백준 / 파이프 옮기기 1 / 17070번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 파이프 옮기기 1 / 17070번 (골드 5단계)

문제 사이트: https://www.acmicpc.net/problem/17070

 

문제 설명

---

나의 풀이

# 파이프 이동 방향
directions = {
    1: [(0, 1, 1), (1, 1, 3)],  # 가로 상태
    2: [(1, 0, 2), (1, 1, 3)],  # 세로 상태
    3: [(0, 1, 1), (1, 0, 2), (1, 1, 3)]  # 대각선 상태
}


# 유효성 검사
def is_valid(home, n, current_status, r, c, dr, dc):
    # 다음 탐색에 충돌이 발생하는 부분이 있는지 확인
    nr, nc = r + dr, c + dc

    # 벽에 부딪치면 더 이상 이동 불가능 판단
    # 범위 확인
    if nr < 0 or nc < 0 or nr >= n or nc >= n:
        return False

    # 대각선 이동인 경우
    if dr == 1 and dc == 1:
        if home[r][c + 1] == 1 or home[r + 1][c] == 1 or home[nr][nc] == 1:
            return False
    else:
        if home[nr][nc] == 1:
            return False

    return True


def search(home, n, current_status, back, front):
    # 전역변수로 가져와 결과값 증가
    global answer

    # 앞 부부분
    r, c = front[0], front[1]

    # n, n에 도착했을 때
    if r == n - 1 and c == n - 1:
        answer += 1
        return

    # 현재 상태에서 다음 상태 확인
    for dr, dc, new_state in directions[current_status]:
        nr, nc = r + dr, c + dc
        
        # 다음 상태에 탐색 가능 여부 확인
        if is_valid(home, n, current_status, r, c, dr, dc):
            search(home, n, new_state, front, [nr, nc])


def main():
    # 결과 값
    global answer
    answer = 0

    # 집의 크기
    n = int(input())
    # 집
    home = []

    # 집의 구조
    for _ in range(n):
        line = list(map(int, input().split()))
        home.append(line)

    # 초기 상태
    initial_status = 1

    # 뒷부분과 앞부분
    back = [0, 0]
    front = [0, 1]

    # 탐색 시작
    search(home, n, initial_status, back, front)
    print(answer)


if __name__ == "__main__":
    main()

DFS를 이용해서 중복 탐색을 거르지 않고 하다보니 O(N^3) 시간 복잡도가 나온 것 같습니다.

# 파이프 이동 방향
directions = {
    1: [(0, 1, 1), (1, 1, 3)],  # 가로 상태
    2: [(1, 0, 2), (1, 1, 3)],  # 세로 상태
    3: [(0, 1, 1), (1, 0, 2), (1, 1, 3)]  # 대각선 상태
}


def search_with_memoization(home, n, current_status, r, c, dp):
    # 이미 도착점에 도달한 경우
    if r == n - 1 and c == n - 1:
        return 1

    # 메모이제이션 값이 존재하면 반환
    if dp[current_status][r][c] != -1:
        return dp[current_status][r][c]

    # 초기 경우의 수
    dp[current_status][r][c] = 0

    # 현재 상태에서 다음 상태 확인
    for dr, dc, new_state in directions[current_status]:
        nr, nc = r + dr, c + dc

        # 다음 상태에 탐색 가능 여부 확인
        if is_valid(home, n, current_status, r, c, dr, dc):
            dp[current_status][r][c] += search_with_memoization(home, n, new_state, nr, nc, dp)

    return dp[current_status][r][c]


# 유효성 검사
def is_valid(home, n, current_status, r, c, dr, dc):
    # 다음 탐색에 충돌이 발생하는 부분이 있는지 확인
    nr, nc = r + dr, c + dc

    # 벽에 부딪치면 더 이상 이동 불가능 판단
    # 범위 확인
    if nr < 0 or nc < 0 or nr >= n or nc >= n:
        return False

    # 대각선 이동인 경우
    if dr == 1 and dc == 1:
        if home[r][c + 1] == 1 or home[r + 1][c] == 1 or home[nr][nc] == 1:
            return False
    else:
        if home[nr][nc] == 1:
            return False

    return True


def main():
    # 집의 크기
    n = int(input())
    home = [list(map(int, input().split())) for _ in range(n)]

    # 초기 상태
    initial_status = 1

    # DP 테이블 초기화 (-1로 초기화)
    dp = [[[-1] * n for _ in range(n)] for _ in range(4)]

    # 탐색 시작
    answer = search_with_memoization(home, n, initial_status, 0, 1, dp)
    print(answer)


if __name__ == "__main__":
    main()

이 풀이는 중복되는 경우의 수를 줄여주는 풀이 즉 모든 가능한 경로의 결과를 누적해서 저장합니다!

---

※ 알아야 할 것

https://velog.io/@eunseokim/BOJ-17070%EB%B2%88-%ED%8C%8C%EC%9D%B4%ED%94%84-%EC%98%AE%EA%B8%B0%EA%B8%B0-1-dp-%ED%92%80%EC%9D%B4-python

[BOJ 17070번] 파이프 옮기기 1 (dp 풀이, python)

다른 사람 풀이입니다!