2186 - 문자판
📚 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로 제출해야 맞았다는 결과를 받을 수 있었던 것 같다.
Author And Source
이 문제에 관하여(2186 - 문자판), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@chang626/2186-문자판저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)