[백준/python] 1987번 : 알파벳

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

 

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

 

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

 

정답

import sys
input = sys.stdin.readline

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

answer = 0
tmp = [(0, 1), (0, -1), (1, 0), (-1, 0)]

stack = set([(0, 0, board[0][0])])  # set으로 안하면 시간초과
while stack:
    x, y, v = stack.pop()
    answer = max(answer, len(v))

    for _x, _y in tmp:
        a = x+_x
        b = y+_y
        if 0 <= a < R and 0 <= b < C and board[a][b] not in v:
            stack.add((a, b, v+board[a][b]))

print(answer)

---

tmp에 상하좌우로 이동하는 좌표값을 저장한다.

 

stack에는 set형태로 현재 위치와 방문한 알파벳 문자열을 넣는다.

처음에는 시작점 (0, 0)과 (0, 0) 위치의 알파벳을 넣는다.

 

stack에서 하나씩 꺼내어 살펴본다.

우선 현재까지 방문한 알파벳 길이를 answer와 비교하여 더 큰 수로 갱신한다.

 

이후 상하좌우 좌표값을 a와 b에 저장하여

인덱스 범위 안에 들어오고 방문한 적이 없는 경우(board[a][b] not in v)

stack에 다음 위치인 (a, b)와 현재까지 방문한 알파벳 + 현재 위치의 알파벳 문자열을 넣는다.