백준: 1987 알파벳

문제

1987번: 알파벳

 

문제 풀이

 그래프를 상, 하, 좌, 우로 탐색하는데 알파벳이 중복되지 않는 한 이동할 수 있다. 이때 최대로 이동할 수 있는 거리를 계산하여 반환하는 문제이다. 처음에는 각 경우에 대해 모두 탐색하여야 한다고 생각하여 백트랙킹을 생각하로 DFS로 작성하였는데, 파이썬으로는 통과할 수 없었다. 따라서 BFS로 풀었는데 BFS 역시 `deque`를 사용하니 메모리 초과가 발생하여 문제를 풀 수 없었다.

 다른 사람들의 풀이를 참고하니, 큐 안에 중복되는 원소가 없으므로 `deque`, `list`보다 속도가 빠른 `set`을 활용하여 큐처럼 활용하니 메모리 문제와 속도 문제를 해결 할 수 있는 것 같았다. 이전에는 백트랙킹의 경우, DFS가 편한다고 생가하였는데 BFS의 경우 필요한 가지만 최종적으로 뻣게 되므로, 경우에 따라 효율적이라는 것을 알 수 있었다.

 

코드

from sys import stdin


def visitable(x, y, alphabets):
    return 0 <= x < r and 0 <= y < c and graph[x][y] not in alphabets


def bfs(start):
    global answer
    q = set([start])
    dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))

    while q:
        cur_x, cur_y, alphabets = q.pop()

        for x, y in dirs:
            next_x, next_y = cur_x + x, cur_y + y
            if visitable(next_x, next_y, alphabets):
                q.add((next_x, next_y, alphabets + graph[next_x][next_y]))
                answer = max(answer, len(alphabets) + 1)


if __name__ == '__main__':
    answer = 1
    r, c = map(int, stdin.readline().split())
    graph = [list(stdin.readline().strip()) for _ in range(r)]
    bfs((0, 0, graph[0][0]))
    print(answer)