문제 바로가기
문제:
알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다. 편의상 모든 문자는 대문자라 생각하자. 예를 들어 아래와 같은 문자판을 보자.
| K | A | K | T |
| X | E | A | S |
| Y | R | W | U |
| Z | B | Q | P |
이 문자판의 한 칸(아무 칸이나 상관없음)에서 시작하여 움직이면서, 그 칸에 적혀 있는 문자들을 차례대로 모으면 하나의 단어를 만들 수 있다. 움직일 때는 상하좌우로 K개의 칸까지만 이동할 수 있다. 예를 들어 K=2일 때 아래의 그림의 가운데에서는 'X' 표시된 곳으로 이동할 수 있다.
| X | ||||
| X | ||||
| X | X | X | X | |
| X | ||||
| X |
반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다. 또, 같은 칸을 여러 번 방문할 수 있다.
이와 같은 문자판과 K, 그리고 하나의 영단어가 주어졌을 때, 이와 같은 영단어를 만들 수 있는 경로가 총 몇 개 존재하는지 알아내는 프로그램을 작성하시오.
위의 예에서 영단어가 BREAK인 경우에는 다음과 같이 3개의 경로가 존재한다. 앞의 수는 행 번호, 뒤의 수는 열 번호를 나타낸다.
- (4, 2) (3, 2) (2, 2) (1, 2) (1, 1)
- (4, 2) (3, 2) (2, 2) (1, 2) (1, 3)
- (4, 2) (3, 2) (2, 2) (2, 3) (1, 3)
입력:
첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다.
출력:
첫째 줄에 경로의 개수를 출력한다. 이 값은 231-1보다 작거나 같다.
풀이:
쉽지 않았던 문제
과거의 풀었던 내리막길과 유사한 풀이
DP를 사용해야한다.
dp 는
dp = [x][y][몇번째]
dp[x][y][idx] 가 이미 메모제이션 되어있으면 그 값을 돌려주면 된다.
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n, m, k = map(int, input().split())
graph = [list(map(str, input())) for _ in range(n)]
word = input().rstrip()
dp = [[[-1 for _ in range(len(word))] for _ in range(m)] for _ in range(n)]
res = 0
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def dfs(x, y, idx):
# 이미 메모제이션 되어있음\
if dp[x][y][idx] != -1:
return dp[x][y][idx]
# 글자 완성
if idx == len(word) - 1:
return 1
dp[x][y][idx] = 0
for i in range(1, k + 1):
for dx, dy in move:
nx = x + (i * dx)
ny = y + (i * dy)
if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == word[idx + 1]:
dp[x][y][idx] += dfs(nx, ny, idx + 1)
return dp[x][y][idx]
print(graph)
for r in range(n):
for c in range(m):
if graph[r][c] == word[0]:
res += dfs(r, c, 0)
print(res)
댓글