백준: 17070 파이프 옮기기 1

문제

17070번: 파이프 옮기기 1

 

문제 풀이

 NxN 격자판에서 파이프를 한쪽 끝 (N, N)으로 이동시키는 방법의 수를 출력하는 문제이다. 파이프는 가로, 세로, 대각선으로 움직일 수 있으며 움직이는 각도는 45도이다. 즉 가로에서 세로, 세로에서 가로는 즉시 변환할 수 없다. 경우의 수를 계산하기 위해 아래와 같이 `DFS`로 풀었다.

 

from sys import stdin


def visitable(x, y, direction):
    if direction == DIAGONAL:
        return x < n and y < n and \
               graph[x - 1][y] == 0 and graph[x][y - 1] == 0 and graph[x][y] == 0

    return x < n and y < n and graph[x][y] == 0


def dfs(loc, direction):
    global answer

    if loc == [n - 1, n - 1]:
        answer += 1

    for next_dir, delta in enumerate(dirs):
        # 45도만 회전시킬 수 있기에, 가로 - 세로, 세로 - 가로는 바로 전환 불가.
        if (direction == SERO and next_dir == GARO) or \
                (direction == GARO and next_dir == SERO):
            continue

        next_x, next_y = loc[X] + delta[X], loc[Y] + delta[Y]

        if visitable(next_x, next_y, next_dir):
            dfs([next_x, next_y], next_dir)


if __name__ == '__main__':
    X, Y = 0, 1
    GARO, SERO, DIAGONAL = 0, 1, 2
    answer = 0
    dirs = [(0, 1), (1, 0), (1, 1)]
    n = int(stdin.readline())
    graph = [list(map(int, stdin.readline().split())) for _ in range(n)]
    dfs([0, 1], 0)
    print(answer)

 예제 1, 2, 3, 4는 정답을 잘 출력하는데 시간 초과가 발생하는 코드이다. 파이프 옮기기 2 문제를 보니, N의 범위가 증가하여 `DP`로 접근하여야 겠다고 생각했다.

 

 `DP`로 풀기 위해서는 (N, N)에 도착하는 경우를 메모이제이션 함으로써 문제를 해결할 수 있다. 

• DP 배열을 `[X][Y][Direction]`으로 구성하여, 좌표에 따라 가로, 세로, 대각선을 접근 가능한 방법을 구한다.
• 대각선으로 이동하기 위해서는 가로, 세로, 대각선에 벽이 없어야 한다.
• 세로, 가로로 이동하기 위해서는 이동하는 방향에 벽이 없어야 한다.
• 각 방향의 점화식은 다음과 같다.
  • 가로 : `dp[x][y - 1][가로] + dp[x][y - 1][대각선]`
  • 세로 : `dp[x - 1][y][세로] + dp[x - 1][y][대각선]`
  • 대각선 : `dp[x - 1][y - 1][가로] + dp[x - 1][y - 1][세로] + dp[x - 1][y - 1][대각선]`
  • 즉 가로, 세로는 이전 좌표의 자신의 방향 + 대각선에서 경로가 진행될 수 있고, 대각선의 경우 모든 경우에서 경로가 진행될 수 있다.
    • 45도로 움직일 수 있다는 문제의 제한조건 때문이다.
• 이와 같은 로직을 반복하면, DP로 문제를 해결할 수 있다.

 

코드

from sys import stdin


if __name__ == '__main__':
    GARO, SERO, DIAGONAL = 0, 1, 2
    n = int(stdin.readline())
    graph = [list(map(int, stdin.readline().split())) for _ in range(n)]

    # [x][y][direction]
    dp = [[[0] * 3 for _ in range(n)] for _ in range(n)]
	
    # 시작 위치 1로 초기화
    dp[0][1][GARO] = 1

    for y in range(2, n):
        if graph[0][y] == 0:
            dp[0][y][GARO] = dp[0][y - 1][GARO]

    for x in range(n):
        for y in range(2, n):
            # 대각선으로 이동하기 위해서는 가로, 세로, 대각선이 벽이 아니어야 함.
            if graph[x][y] == graph[x][y - 1] == graph[x - 1][y] == 0:
                dp[x][y][DIAGONAL] = \
                    dp[x - 1][y - 1][GARO] + dp[x - 1][y - 1][SERO] + dp[x - 1][y - 1][DIAGONAL]

            if graph[x][y] == 0:
                dp[x][y][GARO] = dp[x][y - 1][GARO] + dp[x][y - 1][DIAGONAL]
                dp[x][y][SERO] = dp[x - 1][y][SERO] + dp[x - 1][y][DIAGONAL]

    print(sum(dp[-1][-1]))