[BaekJoon] 백준 1987번 : 알파벳

1987번 : 알파벳

시간초과 때문에 정말 애먹었던 문제였다..

방문 할 곳을 담을 자료구조를 SET 으로 사용하면 시간초과를 해결 할 수 있다.

스택을 이용하여 pop 을 하거나, 큐를 이용하여 popleft 를 하면 전부 시간초과가 발생한다.

다른 사람 풀이를 보면 전부 BFS 를 통해 탐색했다고 하고 SET 을 사용했다.

그런데 SET 을 사용해서 정보를 담으면 어떤게 먼저 pop 될지 모르니 DFS 라고 하기도 그렇고 BFS 라고 하기도 그렇지 않을까..

그냥 그래프 탐색이라고 하면 되려나.. 어쨌든 조금 어려웠던 문제..

---

import sys


def solution():
    global answer, cnt
    dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    stack = {(0, 0, field[0][0])}
    while stack:
        now_i, now_j, path = stack.pop()
        cnt += 1
        answer = max(answer, len(path))

        for value in dirs:
            visit_i, visit_j = now_i + value[0], now_j + value[1]
            if 0 <= visit_i < N and 0 <= visit_j < M and field[visit_i][visit_j] not in path:
                stack.add((visit_i, visit_j, path + field[visit_i][visit_j]))


if __name__ == "__main__":
    answer = -float('inf')
    cnt = 0
    N, M = map(int, input().split())
    field = [list(sys.stdin.readline()) for _ in range(N)]

    solution()
    print(answer)
    print(cnt)