(파이썬) 백준 1987번 "알파벳"

---

# 답

 

from collections import deque
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
board = [input() for _ in range(N)]
chk = [[set() for _ in range(M)] for _ in range(N)]
ans = 1

dy = (1, -1, 0, 0)
dx = (0, 0, 1, -1)

def is_valid_coord(y, x):
    return 0 <= y < N and 0 <= x < M

def bfs(sy, sx):
    global ans
    q = deque()
    q.append((sy, sx, board[sy][sx]))
    chk[sy][sx].add(board[sy][sx])

    while q:
        y, x, s = q.popleft()
        ans = max(ans, len(s))
        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if is_valid_coord(ny, nx) and board[ny][nx] not in s:
                ns = s + board[ny][nx]
                if ns not in chk[ny][nx]:
                    chk[ny][nx].add(ns)
                    q.append((ny, nx, ns))

bfs(0, 0)
print(ans)

 

 

 

 

 

---

# 분석

 

단순히 DFS / BFS로만 풀면 시간초과가 납니다. 따라서 백트래킹까지 구현해주어야 합니다.

우선 아래 격자판을 보며 ① → ④ 로 가는 경로를 생각해봅시다.

일반적으로 생각한다면 2가지 경로가 존재합니다.

 

① → ② → ④ 

또는

① → ③ → ④ 

 

 

 

하지만 이 문제에서 두 경로는 완전히 똑같은 경로입니다. 지나온 칸 수도 똑같고, 지나오면서 마주친 문자가 B인 것도 똑같기 때문입니다. 두 경로는 'A → B → C'라는 정확히 똑같은 경로를 따릅니다. 따라서 둘 중 하나의 경우만 확인해보면 나머지 하나는 또 확인할 필요가 전혀 없습니다.

 

제 임의로 ① → ② → ④ 과 같은 경로를 '좌표 경로', A → B → C 와 같은 경로를 '알파벳 경로'라고 부르겠습니다.

이제 코드를 보겠습니다.

 

백트래킹을 위해 아래와 같은 chk 변수를 생성합니다.

모든 칸에 대하여 집합 set을 각각 만들고, 이를 이중 리스트로 만들어서 변수 chk에 담았습니다.

chk = [[set() for _ in range(M)] for _ in range(N)]

 

bfs 함수 내부를 살펴보겠습니다.

파란색으로 표시해 둔 곳을 집중해서 봐 주세요.

 

아까 위의 예시에서 ① → ② → ④ 와 ① → ③ → ④ 가 다른 경로처럼 보이지만 사실은 'A → B → C' 라는 똑같은 경로를 가지고 있다고 했었죠? 이 'A → B → C' 알파벳 경로에 해당하는 것이 위 코드에서 문자열 변수 s와 ns에 담긴다고 생각하시면 됩니다.

'좌표 경로'로는 중복이 걸러지지 않으므로, '알파벳 경로(ns)'를 생성해서 집합에 담아둠으로써 나중에 또 똑같은 알파벳 경로로 탐색을 할 수 없게끔 중복을 차단합니다.