[백준] 1987번 알파벳 (Python)

백준 1987 알파벳

DFS탐색을 하기 위해 열심히 노력했지만 시간 초과의 벽을 넘지 못했다. 결국 BFS탐색이 답이라 생각하고 deque를 활용해 풀었지만, 여전히 시간 초과의 벽을 넘지 못했다. 구글링을 통해 힌트를 얻었고 set을 활용한 BFS탐색에 대해 알게 되었다.

set VS deque

BFS 탐색을 할 때는 언제나 deque를 사용했는데 set을 사용할 때가 더 유리한 경우가 있다. 어떤 자료구조가 더 빠른지 판단하기 위해선 문제를 제대로 파악해야 한다.

1. set을 사용하면 중복이 제거된다는 것은 알고 있지만, 과연 중복 제거가 의미가 있을까?
   • 그렇다. 같은 좌표에 다른 루트로 도달했더라도 현재까지 지나온 알파벳이 같다면 같은 경우로 해석해도 무방하다.
2. 최단거리를 구하는 것이 아니기 때문에 모든 경우를 탐색해야 한다. 즉, deque를 활용해서 더 빠른 알고리즘의 종료를 기대할 수 없다.

이러한 이유로 set을 활용해서 BFS 탐색을 진행하면 통과할 수 있다. 또한, 지금까지 지나온 알파벳을 저장하기 위해서 String을 활용했다.

import sys

def BFS():
    q = set([(0, 0, 1, grid[0][0])])
    res = 0
    while q:
        y, x, cnt, s = q.pop()
        res = max(res, cnt)
        for d in range(4):
            tmpY = y + dy[d]
            tmpX = x + dx[d]
            if n > tmpY >= 0 and m > tmpX >= 0 and grid[tmpY][tmpX] not in s:
                    q.add((tmpY, tmpX, cnt + 1, s + grid[tmpY][tmpX]))
    return res

input =sys.stdin.readline
n , m = map(int, input().split())
grid= []
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
for _ in range(n):
    grid.append(input().strip())
print(BFS())