[ 백준 17070 ] 파이프 옮기기 1

 

문제 보기

이 문제는 백트랙킹(Backtracking) 문제이다. N의 최댓값이 16이기 때문에 dp가 아닌 백트랙킹으로도 충분히 통과할 수 있다고 생각하였다.

 

파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 구해야 한다. 파이프는 이동하는 방향을 통해 다른 한쪽을 추측할 수 있으므로 바깥쪽 칸만 저장한다. (실제로는 추측할 필요도 없다)

 

알고리즘 과정은 아래와 같다.

1. 인덱스가 (N - 1, N - 1)인지 확인한다.

2. 가로 방향으로 이동할 수 있는지 파악한다.

   -  (현재 방향(가로 or 대각선)과 이동하고자 하는 위치 벽인지 확인)

3. 세로 방향으로 이동할 수 있는지 파악한다.

   -  (현재 방향(세로 or 대각선)과 이동하고자 하는 위치 벽인지 확인)

4. 대각선 방향으로 이동할 수 있는지 파악한다.

   -  (대각선 이동이 가능한지 3가지 위치 벽 확인)

5. 위 과정을 더 이상 동작하지 않을 때까지 반복한다.

 

코드

def Backtracking(r, c, d):
    global answer

    if r == N - 1 and c == N - 1:
        answer += 1
    else:
        # 가로
        if d == 0 or d == 2:  # 가로 혹은 대각선 방향일때 가로로 이동 가능.
            if c + 1 < N and arr[r][c + 1] == 0:
                Backtracking(r, c + 1, 0)

        # 세로
        if d == 1 or d == 2:  # 세로 혹은 대각선 방향일때 세로로 이동 가능
            if r + 1 < N and arr[r + 1][c] == 0:
                Backtracking(r + 1, c, 1)

        # 대각선
        if r + 1 < N and c + 1 < N:
            if arr[r + 1][c] == arr[r][c + 1] == arr[r + 1][c + 1] == 0:
                Backtracking(r + 1, c + 1, 2)


if __name__ == "__main__":
    # input
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]

    answer = 0
    Backtracking(0, 1, 0)
    print(answer)