📚 2186 - 문자판

문자판

이해

n, m 크기의 문자판이 주어지며, 경로의 개수를 구하는 문제이다.
직사각형과 경로가 등장했다.
이는 깊이 우선 탐색, 너비 우선 탐색으로 풀 수 있는 문제라는 것이다.
보통 우선 탐색 문제들은 좌표안에서 지나갈 수 있는 경로를 구할 때 많이 사용된다.

📌 주의점
출력 값이 2^31 - 1 보다 작거나 같기 때문에, 메모이제이션을 사용하여 계산들을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 해야 한다.

➡️ 메모이제이션을 사용해야 하므로 깊이 너비 탐색을 사용해야 한다.

입력 마지막 줄에 영단어가 주어지는 데 이 단어를 통해 문자판에서 찾을 때, 마지막 줄의 첫 번째 단어를 통해 시작 점이 어딘지 찾으면 된다.
그리고 나서 그 위치를 기준으로 깊이 너비 탐색을 하면 된다.
다만, K 만큼 이동할 수 있으므로 현재 위치에서 이동할 수 있는 공간을 상하좌우로 + k 만큼 검토하여 찾는다.

소스

import sys
from collections import deque

x_coordinate = [-1, 0, 1, 0]
y_coordinate = [0, 1, 0, -1]

read = sys.stdin.readline

n, m, k = map(int, read().split())

arr = []

for i in range(n):
    arr.append(list(map(str, read().strip())))

find_data = list(map(str, read().strip()))


def dfs(cur_x, cur_y, cur_data_idx):
    # 만약 현재 찾는 인덱스가 문자열 길이보다 클 경우
    if cur_data_idx == len(find_data):
        return 1
    # 현재 방문한 곳이라면 종료
    if arr_result_space[cur_x][cur_y][cur_data_idx] != -1:
        return arr_result_space[cur_x][cur_y][cur_data_idx]

    arr_result_space[cur_x][cur_y][cur_data_idx] = 0
    for i in range(4):
        for k_idx in range(1, k + 1):
            next_x = x_coordinate[i] * k_idx + cur_x
            next_y = y_coordinate[i] * k_idx + cur_y

            if 0 <= next_x < n and 0 <= next_y < m:
                if find_data[cur_data_idx] == arr[next_x][next_y]:
                    arr_result_space[cur_x][cur_y][cur_data_idx] += dfs(next_x, next_y, cur_data_idx + 1)
    return arr_result_space[cur_x][cur_y][cur_data_idx]


result = 0

arr_result_space = [[[-1] * len(find_data) for _ in range(m)] for _ in range(n)]

for i in range(n):
    for j in range(m):
        if arr[i][j] == find_data[0]:
            result += dfs(i, j, 1)

print(result)

채점 결과

Python3는 주어진 메모리 2배 + 32MB 보너스를 받는다.
PyPy3는 주어진 메모리 2배 + 128M 보너스를 받는다.

아마 메모리의 크기가 많이 필요한 문제라서 PyPy3로 제출해야 맞았다는 결과를 받을 수 있었던 것 같다.