코딩테스트 스터디 - 백준 2186번 : 문자판 (python)

문제

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

2186번: 문자판

요약

N*M크기의 문자판이 있다.

이 문자칸의 어떤 칸에서 한번에 십자방향으로 K칸까지 움직일 수 있다.

특정 단어를 만들 수 있는 경로의 경우의 수를 구하는 문제다.

의식의 흐름

처음에는 DFS를 떠올렸다.

예를들어 단어가 BREAK면, 맵에서 B를 찾아 거기서부터 K칸이내로 REAK를 찾고,

R을 찾았으면 거기서부터 K칸 이내로 EAK를 찾고, 이렇게 재귀적으로 구현할 수 있다.

하지만 이렇게 할 경우 단어 길이가 최대 80자인데, N*M*4K^80의 시간복잡도를 가진다.

 

그러다가 생각난게 같은 칸을 여러번 방문할 것 같다는 점이었다.

예를들어 BRB 형태로 맵이 있으면, 첫 B를 방문할때와 둘째 B를 방문할 때 dfs(R)을 두 번 실행하게 된다.

따라서 DP로 구현하기로 했다.

이번엔 글자 맨 뒤에서부터 시작해 테이블에 지금까지의 sub단어를 만들 수 있는 경우의수를 저장하는 방식이다.

테이블을 표현하면 찾을 단어를 word라 할때,

table[i][j][t] = board[i][j] 칸을 시작점으로 word[-t : ] 단어를 만들 수 있는 경우의 수 가된다.

t가 하나 늘어날 때마다, 특정 칸에서 갈 수 있는 범위(십자범위의 K칸) 내에 있는 값들 전 테이블에서 찾아서 다 더해주면 된다. 

이렇게 하면 시간 복잡도가 N*M*4K*80이 된다!

구현

자료구조

DP 테이블을 이용한다.

t번째 table[i][j] = board[i][j] 칸을 시작점으로 word[-t : ] 단어를 만들 수 있는 경우의 수를 저장한다.

다만 옛날 테이블까지 저장할 필요는 없으므로, table과 new_table을 사용해 직전 테이블만 저장한다.

알고리즘

우선 기본적인 철학은

E에서 EAK를 만드는 경우의 수 = 그 E 주변에 있는 A에서 AK를 만드는 경우의 수의 합 이다.

 

단어를 뒤에서부터 순회해 뒤에서부터 n번째 글자와 n-1번째 (바로다음) 글자를 가지고 new_table을 구성한다.

예를들어 BREAK 면 A와 K, E와 A, ... 이런식이다.

n번째 글자가 있는 위치 [i][j]에서,

new_table[i][j] = [i][j]에서 갈 수 있는 칸 중 n-1번째 글자가 있는 곳의 table 값들의 합

그리고 순회가 끝나면 table = new_table로 업데이트시켜준다.

코드

이번에는 처음으로 적절한 알고리즘을 선택했다는 뿌듯함이 있었다.

경우의 수 문제는 DP를 먼저 고려해봐야되겠다.

또 직접 코드를 짜기전에, 총 몇번의 iteration이 이뤄지는지 정도는 대충 계산해 봐야겠다는 생각이 들었다.

 

'''
    문제 출처 : https://www.acmicpc.net/status?user_id=yjl980730&problem_id=2186&from_mine=1
'''
N, M, K = list(map(int, input().split(' ')))
board = []
for i in range(N):
    board.append(input())

target = input()

deltas = [(0,1), (0,-1), (1,0), (-1,0)]
def get_poses(i, j):
    global board, K, N, M
    poses = []
    for k in range(K):
        for delta in deltas:
            x = i + delta[0] * (k+1)
            y = j + delta[1] * (k+1)
            if x < 0 or y < 0 or x > N-1 or y > M-1:
                continue
            poses.append((x,y))
    return poses



table = [[0 for i in range(M)] for j in range(N)]

for i in range(N):
    for j in range(M):
        if board[i][j] == target[-1]:
            table[i][j] = 1

for l in range(1, len(target)):
    letter = target[len(target) - 1 - l]
    last_letter = target[len(target) - l]
    new_table = [[0 for i in range(M)] for j in range(N)]
    for i in range(N):
        for j in range(M):
            if board[i][j] == letter:
                for pos in get_poses(i, j):
                    if board[pos[0]][pos[1]] == last_letter:
                        new_table[i][j] += table[pos[0]][pos[1]]
    table = new_table
print(sum(map(sum, table)))