[BOJ] 2186 / 문자판 / Python 파이썬

[BOJ] 2186 / 문자판 / Python 파이썬

[BOJ] 2186 / 문자판 / Python 파이썬

https://www.acmicpc.net/problem/2186

2186번: 문자판

 

풀이

주어진 조건을 만족하는 모든 경로의 개수를 구하는 문제이다.

 

모든 경로는 DFS 를 이용하여 구현하였지만, 시간초과에 부딪히고 말았다.

 

모든 경로에 대한 완전탐색의 최적화는, 각 진행상황에 대해 memorization 을 해주며 중복하여 탐색하는 경우를 제거해 주어야 하였다.

그래서 visited를 2차원 배열이 아닌 3차원 배열로 만들어주고, 각 좌표값과 진행상태에 수를 저장해 주어 해결하였다.

 

※진행상황은 완전탐색을 하며 언제든 다시 진입 할 수 있으니, 최대한 모든 경우를 저장하는 방향으로 구현해 주어야 하였다.

 

import sys

input = sys.stdin.readline

N, M, K = map(int, input().split())

maps = []

for _ in range(N):
    maps.append(input().rstrip())

word = input().rstrip()

visited = [[[-1] * len(word) for _ in range(M)] for _ in range(N)]


def DFS(y, x, idx):
    global N, M, K, word
	
    # 이전에 진입한 경우
    if visited[y][x][idx] != -1:
        return visited[y][x][idx]

	# 진행상황과 글자가 맞지 않는 경우 / 다른 경로지만 같은 단계로 진입하는 경우를 고려
    if maps[y][x] != word[idx]:
        return 0

	# 글자 탐색완료
    if idx == len(word)-1:
        return 1

    cnt = 0
    for i in range(-K, K+1):
        if not i:
            continue
            
        # 최대한 모든 경우에 대해 탐색
        if 0 <= y+i < N:
            cnt += DFS(y+i, x, idx+1)
            
        # 최대한 모든 경우에 대해 탐색
        if 0 <= x+i < M:
            cnt += DFS(y, x+i, idx+1)
    visited[y][x][idx] = cnt
    return cnt


res = 0
for n in range(N):
    for m in range(M):
        if maps[n][m] == word[0]:
            res += DFS(n, m, 0)

print(res)