[ 백준 1987 ] 알파벳

문제

백준 1987번

정말 오랜만에 풀어본 알고리즘 문제...
파이썬 문법부터 헷갈려서 구글링을 해가며 풀었다😂

풀이

틀린 풀이

import sys
from collections import deque
input = sys.stdin.readline

d = ((1, 0), (-1, 0), (0, 1), (0, -1))

R, C = map(int, input().split())
arr = [list(input()) for _ in range(R)]

x, y = 0, 0
queue = set()
queue.add((x, y, arr[0][0]))
visited = {(x, y)}
answer = 1

while queue:
    x, y, alpha = queue.pop()
    answer = max(answer, len(alpha))
    for i in range(4):
        nx = x + d[i][0]
        ny = y + d[i][1]
        if nx < 0 or nx >= R or ny < 0 or ny >= C:
            continue
        if (nx, ny) in visited or arr[nx][ny] in alpha: 
            continue
        visited.add((nx, ny))
        queue.add((nx, ny, alpha + arr[nx][ny]))

print(answer)

최단경로를 찾는 문제와 풀이를 헷갈려서 저런식으로 풀어놨다.
if (nx, ny) in visited 이런식으로 방문체크를 했던 것이 잘못이었다.
이 문제는 최단경로를 찾는 문제와 달리 어떤 지점에서 앞으로 몇 칸 갈 수 있는지는 이전 경로에 따라 달라지기 때문에, 다른 경로에서 이미 가본 칸이라고 해서 넘겨버려서는 안 된다...

맞는 풀이

import sys
from collections import deque
input = sys.stdin.readline

d = ((1, 0), (-1, 0), (0, 1), (0, -1))

R, C = map(int, input().split())
arr = [list(input()) for _ in range(R)]

x, y = 0, 0
queue = set()
queue.add((x, y, arr[0][0]))
answer = 1

while queue:
    x, y, alpha = queue.pop()
    answer = max(answer, len(alpha))
    for i in range(4):
        nx = x + d[i][0]
        ny = y + d[i][1]
        if nx < 0 or nx >= R or ny < 0 or ny >= C:
            continue
        if arr[nx][ny] in alpha: 
            continue
        queue.add((nx, ny, alpha + arr[nx][ny]))

print(answer)

각각의 라운드에서 지나온 경로(alpha)에 다음 알파벳이 포함되어있는지를 체크하면, 굳이 방문체크를 할 필요가 없다!

출처

참고한 코드: 1987 - 알파벳 - 파이썬