[백준] 1987번 알파벳 (파이썬)

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

1987번: 알파벳

 

<코드>

from sys import stdin
R, C = map(int, stdin.readline().split())
arr = [list(stdin.readline().strip()) for _ in range(R)]
queue = set([(0, 0, arr[0][0])])

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
result = 1
while queue:
    r, c, ans = queue.pop()
    for d in range(4):
        nr = r + dr[d]
        nc = c + dc[d]
        if 0 <= nr < R and 0 <= nc < C and not arr[nr][nc] in ans:
            queue.add((nr, nc, ans+arr[nr][nc]))
            result = max(result, len(ans)+1)

print(result)

 

<풀이방법>

1. bfs로 접근하여 인자에 r,c 뿐아니라 문자열 길이를 더 한 값을 함께 넣어서 가장 긴 길이를 구하였다.

 

<리뷰>

처음에 리스트로 풀었는데 계속 시간초과가 떠서 어떻게 풀어야할지 몰라서 구글링을 하였다.

set은 시간복잡도가 O(1)이고 리스트는 시간복잡도가 O(n)이라 queue를 list 대신 set으로 바꿔서 푸니까 됐다.