[백준알고리즘] 2186번: 문자판 -Python

[백준알고리즘] 2186번: 문자판 -Python

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

2186번: 문자판

일단 파이썬보다는 PyPy로 통과할 확률이 높다.

 

이번 문제에서도 BFS 혹은 DFS를 통해서 주어진 문자열을 모두 완성할 수 있는 경우의 수를 구해주면 된다고 생각했다. 처음에는 이전에 몇 번 풀었던 것처럼 방문 여부를 확인하는 visit을 딕셔너리로 했다. 이유는 (i, j)에 내가 위치했었다고 했을 때, 단순하게 방문 여부만 체크하면 안되기 때문이다.

 

예를 들어 주어진 K가 1일때 다음 표에서 BEER를 만들 수 있는 경우의 수를 구한다고 해보자.

XXBX

BEER

XBXX

 

1. (1, 0)→(1, 1)→(1, 2)→(1, 3)
2. (2, 1)→(1, 1)→(1, 2)→(1, 3)

다음과 같이 두가지 경로가 존재할 수 있다.

여기서 (1, 1)→(1, 2)→(1, 3) 이부분은 중복돼서 들어간다. 그렇다면 1번째 방문 시 (1, 1), (1, 2), (1, 3) 모두에 1을 저장하고 두번째 방문 시에는 이 중에 한 곳을 방문하면 더 이상 진행하지 않고 1의 경우의 수를 추가해도 되는가?

 

그렇지 않다.

 

(0, 2)에도 B가 있다. 하지만 이 좌표에서 시작을 하게 된다면 BEER를 완성할 수 없게 된다. (1, 2)까지는 방문할 수 있으나 그 이후를 제대로 완성할 수 없다. 하지만 (1, 2)를 한 번 방문했었다고 이 경로도 더 이상 진행하지 않고 경우의 수를 포함시키면 안 된다.

 

 

그렇기 때문에 각각의 좌표는 문자열에서 몇번째 문자를 인덱싱 하는지도 관리를 해야한다는 것이다.

따라서 (1, 1) 좌표에서 BEER의 1번 index에 해당하는 E를 찾으려 할 때 이미 완성된 경로가 1개 존재한다는 것을 의미한다고 표시해주어야 한다.

마찬가지로 (1, 2)좌표에서는 BEER의 2번 index에 해당하는 E를 찾으려 할 때 이미 완성된 경로가 1개 존재한다는 것을 의미하게 된다.

 

그렇기 때문에 (0, 2)에 위치한 B에서 시작할 때, (1, 2)를 방문하면, BEER의 1번 index에 해당하는 E를 찾기 위함으로, 이 경우에 대해서는 조사한 적이 없기 때문에 조사를 별도로 해주어야 하는 것이다.

 

 

이렇게까지 개념은 잘 만들고 코딩을 했었으나, 시간초과가 발생했다.

 

기존에는 다음과 같이 딕셔너리에 리스트를 만들거나 딕셔너리 키를 각각 해주었는데, 잦은 생성 및 리스트 확장으로 시간 초과가 발생한 것 같다.

• visit[(i, j)] = [(index1, value1), (index2, value2)]
• visit[(i, j, index)] = value

 

아래처럼 애초에 visit을 3중 리스트를 통해 만들어주고 값만 변경해주었더니 여유롭게 통과할 수 있었다.

import sys
sys.setrecursionlimit(10**9)
 
def solve(i, j, depth):
    if visit[i][j][depth] >= 0:
        return visit[i][j][depth]
    
    if table[i][j] != target[depth]:
        visit[i][j][depth] = 0
        return 0
 
    depth += 1
    if depth == len_target:
        visit[i][j][depth-1] = 1
        return 1
    
    cnt = 0
    for t in range(-k, k+1):
        if t == 0: continue
        
        it, jt = i+t, j+t
        if 0 <= it < n:
            cnt += solve(it, j, depth)
        if 0 <= jt < m:
            cnt += solve(i, jt, depth)
    visit[i][j][depth-1] = cnt
    return cnt
 
n, m, k = map(int, sys.stdin.readline().split())
table = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
target = sys.stdin.readline().rstrip()
len_target = len(target)
 
visit = [[ [-1]*len_target for j in range(m)] for i in range(n)]
ans = 0
for i in range(n):
    for j in range(m):
        if table[i][j] == target[0]:
            ans += solve(i, j, 0)
print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다