백준 1987 - 알파벳 (Python)

https://acmicpc.net/problem/1987 

1987번: 알파벳

깨달음이 있었던 문제. bfs 자리에 set을 넣을 수 있다는 생각 자체를 해보지 않았는데, 알게 되었다.

즉 특정 좌표에서 특정 visited 상태로 다시 진입하지 않을 수 있도록 q를 set으로 두는 것이다.

알파벳의 종류를 ord()를 이용하여 int 로 전달해보기도 하고, 비트 연산으로 전달해보기도 하였으나 전부 시간초과였다.

import sys

input = sys.stdin.readline
r, c = map(int, input().split())
answer=1
graph = []
for _ in range(r):
    graph.append(list(input()))

dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]


def bfs():
    global answer
    q = set([(0, 0, graph[0][0])])
    while q:
        cur_y, cur_x, visited = q.pop()
        for i in range(4):
            ny = cur_y + dy[i]
            nx = cur_x + dx[i]
            if 0 <= ny < r and 0 <= nx < c:
                al = graph[ny][nx]
                if al not in visited:
                    q.add((ny, nx,visited+al))
                    answer=max(answer,len(visited)+1)


    return answer

print(bfs())