백준 1987번 (골드 4) : 알파벳

https://www.acmicpc.net/problem/1987

1987번: 알파벳

- 기본적인 생각은 처음부터 옳았으나, queue에 들어가는 아이들 중에서 중복이 있을 수 있다는 것을 전혀 생각하지 못하고 계속해서 deque를 이용해서 queue를 구현해서 사용했다.

- 이 때문에 계속 시간 초과가 났고, 결국 set을 이용해서 queue를 구현하자 중복이 제거되어서 시간 초과가 해소되었다.

import sys

r,c = map(int, sys.stdin.readline().rstrip().split())

maps = []

for _ in range(r):
    maps.append(list(sys.stdin.readline().rstrip()))

def bfs(maps):
    queue = set([(0,0,maps[0][0],1)])
    maximum = 1
    moves = [[1,0], [-1,0], [0,1], [0,-1]]
    while queue:
        nowy, nowx, nowstr, count= queue.pop()
        if maximum < count:
            maximum= count
        for my, mx in moves:
            dy = my + nowy
            dx = mx + nowx

            if dy<0 or dy>=r or dx<0 or dx>= c:
                continue

            if maps[dy][dx] not in nowstr:
                if count+1 == 26:
                    return 26
                queue.add((dy,dx,nowstr+maps[dy][dx], count+1))

    return maximum

print(bfs(maps))