문제 링크: https://www.acmicpc.net/problem/17070

Thumbnail: Photo by Samuel Sianipar (Unsplash)

DFS/BFS의 그래프 탐색으로 푸는 문제이지만, 그냥 풀면 시간 초과를 맞닥뜨리게 되는 문제였습니다.

풀이

DFS

[\((0, 0), (0, 1)\)]에 가로로 배치되어있는 파이프를 오른쪽 / 아래 / 대각선의 3가지 방향으로 밀면서 \((N, N)\)으로 옮길 수 있는 경우의 수를 구하는 문제입니다. 단, \(N \times N\) 모양의 격자 구조의 방에는 일부 공간에 벽이 존재하며, 파이프는 벽이 있는 칸을 지날 수 없습니다.

이런 형태의 문제는 DFS/BFS의 그래프 탐색 기법을 활용해 풀 수 있습니다. DFS를 택했습니다.

먼저 전형적인 DFS 형태를 작성해 봅시다.

DFS의 인자로 전달할 변수는 3가지입니다.

• r, c: 현재 파이프의 우측 하단 좌표입니다. 이 좌표가 \(N, N\)에 도달하면 탐색을 종료합니다.
• direction: 현재 파이프의 배치 상태를 나타내는 0~2의 상수입니다. 코드에서는 가독성을 위해 상수로 선언 후 사용했습니다.

# Constants
RIGHT = EMPTY = 0
DOWN = 1
DIAGONAL = 2

def dfs(r, c, direction):
    if r == N - 1 and c == N - 1:
        return 1
    
    count = 0
    ...

    return count

dfs(0, 1, RIGHT)

이제, 파이프가 배치된 방향에 따라 갈 수 있는 경우의 수를 생각해 봅시다.

1) 파이프의 방향이 '오른쪽'일 때

현재 칸 \((r, c-1), (r, c)\)에 파이프가 있습니다. 이때,

1. \((r, c+1)\)도 빈 칸이라면 오른쪽으로 이동이 가능합니다.
   dfs(r, c+1, RIGHT)
2. \((r, c+1), (r+1, c), (r+1, c+1)\)가 모두 빈칸이라면 대각선으로 이동이 가능합니다.
   dfs(r+1, c+1, DIAGONAL)

2) 파이프의 방향이 '아래'일 때

현재 칸 \((r-1, c), (r, c)\)에 파이프가 있습니다. 이때,

1. \((r+1, c)\)도 빈 칸이라면 아래로 이동이 가능합니다.
   dfs(r+1, c, DOWN)
2. \((r, c+1), (r+1, c), (r+1, c+1)\)가 모두 빈칸이라면 대각선으로 이동이 가능합니다.
   dfs(r+1, c+1, DIAGONAL)

3) 파이프의 방향이 '대각선'일 때

현재 칸 \((r-1, c-1), (r, c)\)에 파이프가 있습니다. 이때,

1. \((r, c+1)\)도 빈 칸이라면 오른쪽으로 이동이 가능합니다.
   dfs(r, c+1, RIGHT)
2. \((r+1, c)\)도 빈 칸이라면 아래로 이동이 가능합니다.
   dfs(r+1, c, DOWN)
3. \((r, c+1), (r+1, c), (r+1, c+1)\)가 모두 빈칸이라면 대각선으로 이동이 가능합니다.
   dfs(r+1, c+1, DIAGONAL)

이 조건을 DFS 코드에 반영해 재귀 구문을 작성해봅시다.

N = int(input())
Room = tuple(tuple(map(int, input().split())) for _ in range(N))   # N x N 크기의 격자

# Constants
RIGHT = EMPTY = 0
DOWN = 1
DIAGONAL = 2

def dfs(r, c, direction):
    if r == N - 1 and c == N - 1:
        return 1
    
    count = 0 # 현재 DFS에서 계산된 (N, N)에 도달할 수 있는 경우의 수

    # 현재 파이프의 방향에 따라서 다음 위치 계산하기
    if direction == RIGHT:
        if c < N - 1 and Room[r][c+1] == EMPTY:
            if r < N - 1 and Room[r+1][c] == EMPTY and Room[r+1][c+1] == EMPTY:
                count += dfs(r + 1, c + 1, DIAGONAL)
            count += dfs(r, c + 1, RIGHT)
    elif direction == DOWN:
        if r < N - 1 and Room[r+1][c] == EMPTY:
            if c < N - 1 and Room[r][c+1] == EMPTY and Room[r+1][c+1] == EMPTY:
                count += dfs(r + 1, c + 1, DIAGONAL)
            count += dfs(r + 1, c, DOWN)
    else: # DIAGONAL
        if c < N - 1 and Room[r][c+1] == EMPTY:
            if r < N - 1 and Room[r+1][c] == EMPTY and Room[r+1][c+1] == EMPTY:
                count += dfs(r + 1, c + 1, DIAGONAL)
            count += dfs(r, c + 1, RIGHT)
        if r < N - 1 and Room[r+1][c] == EMPTY:
            count += dfs(r + 1, c , DOWN)

    return count

print(dfs(0, 1, RIGHT))

하지만, 이대로 DFS를 진행하게 되면 시간 초과가 발생합니다. 문제에서, 방 크기인 \(N\)은 \(3 \le N \le 16\)으로 범위가 정해져 있습니다. \(N = 16\)인 경우 위 코드는 시간 초과를 받을겁니다.

그렇다면 어떻게 해결할 수 있을까요? 답은 DP에 있습니다. DP에 관한 설명은 이전 글을 읽어보길 바랍니다 😉

DFS의 과정도 결국 재귀를 통해 다음 위치를 탐색하는 것입니다. 만약 이 과정에서 중복되는 재귀 호출이 일어난다면, 이를 DP를 통해 최적화 할 수 있다면 시간을 단축할 수 있습니다.

결국 dfs(r, c, direction)함수가 계산하는 결과는 매개변수가 같다면 반드시 결과가 같을 것이라 기대할 수 있습니다. 즉, DP의 조건인 '최적 부분 구조'와 '겹치는 부분 문제'가 성립합니다.

이 문제에서는 재귀 호출 풀이인 DFS를 사용하고 있으므로, DP 기법인 Memoization을 사용했습니다. dfs(r, c, direction)의 매개변수를 키로 가지는 Map을 캐시로 사용해, 이전에 탐색한 부분 문제라면 다시 계산하는 대신 캐시에 저장된 결과 값을 재활용했습니다.

cache = {}
def dfs(r, c, direction):
    if r == N - 1 and c == N - 1:
        return 1
    if (r, c, direction) in cache:
        return cache[(r, c, direction)]
    
    count = 0   
    if direction == RIGHT:
        if c < N - 1 and Room[r][c+1] == EMPTY:
            if r < N - 1 and Room[r+1][c] == EMPTY and Room[r+1][c+1] == EMPTY:
                count += dfs(r + 1, c + 1, DIAGONAL)
            count += dfs(r, c + 1, RIGHT)
    elif direction == DOWN:
        if r < N - 1 and Room[r+1][c] == EMPTY:
            if c < N - 1 and Room[r][c+1] == EMPTY and Room[r+1][c+1] == EMPTY:
                count += dfs(r + 1, c + 1, DIAGONAL)
            count += dfs(r + 1, c, DOWN)
    else: # DIAGONAL
        if c < N - 1 and Room[r][c+1] == EMPTY:
            if r < N - 1 and Room[r+1][c] == EMPTY and Room[r+1][c+1] == EMPTY:
                count += dfs(r + 1, c + 1, DIAGONAL)
            count += dfs(r, c + 1, RIGHT)
        if r < N - 1 and Room[r+1][c] == EMPTY:
            count += dfs(r + 1, c , DOWN)

    cache[(r, c, direction)] = count
    return count

print(dfs(0, 1, RIGHT))

전체 코드

input = open(0).readline
N = int(input())
Room = tuple(tuple(map(int, input().split())) for _ in range(N))   # N x N 크기의 격자

# Constants
RIGHT = EMPTY = 0
DOWN = 1
DIAGONAL = 2

cache = {}
def dfs(r, c, direction):
    if r == N - 1 and c == N - 1:
        return 1
    if (r, c, direction) in cache:
        return cache[(r, c, direction)]
    
    count = 0   
    if direction == RIGHT:
        if c < N - 1 and Room[r][c+1] == EMPTY:
            if r < N - 1 and Room[r+1][c] == EMPTY and Room[r+1][c+1] == EMPTY:
                count += dfs(r + 1, c + 1, DIAGONAL)
            count += dfs(r, c + 1, RIGHT)
    elif direction == DOWN:
        if r < N - 1 and Room[r+1][c] == EMPTY:
            if c < N - 1 and Room[r][c+1] == EMPTY and Room[r+1][c+1] == EMPTY:
                count += dfs(r + 1, c + 1, DIAGONAL)
            count += dfs(r + 1, c, DOWN)
    else: # DIAGONAL
        if c < N - 1 and Room[r][c+1] == EMPTY:
            if r < N - 1 and Room[r+1][c] == EMPTY and Room[r+1][c+1] == EMPTY:
                count += dfs(r + 1, c + 1, DIAGONAL)
            count += dfs(r, c + 1, RIGHT)
        if r < N - 1 and Room[r+1][c] == EMPTY:
            count += dfs(r + 1, c , DOWN)

    cache[(r, c, direction)] = count
    return count

print(dfs(0, 1, RIGHT))