[백준] 1987번 알파벳 [Python]

 

 

RxC 크기의 보드 각 칸에 알파벳이 놓여있다.

 

현재 말이 $($1, 1$)$에 놓여 있고, 상하좌우로 인접한 칸으로 이동 가능하고,

한 번도 마주친적 없는 알파벳이 있는 곳으로만 이동 가능합니다.

 

말이 최대 지날 수 있는 칸 수를 구하는 문제

 

문제

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

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

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

입력

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

출력

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

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

 

알파벳의 개수가 26개라서 가능한 최대 길이는 26이다.

 

문자를 숫자로 바꿔서 저장하고, 상하좌우로 보드 판 내에서 탐색한다.

 

대문자는 아스키 코드에서 65에서 90 사이의 값을 가진다.

그 값에 65를 빼서 0~25로 변경후 2의 거듭제곱 꼴로 바꿔서 저장한다.

>>> 이진법으로 나타내면 중복 여부를 쉽게 확인할 수 있다.

 

&로 같은 숫자가 있는지 확인하고 지나간 구간의 값은 |로 추가한다.

 

import sys
input = sys.stdin.readline

R, C = map(int, input().split())
L = R*C
graph = []
for _ in range(R):
    graph.extend(list(map(lambda x:1 << ord(x)-65, input().rstrip())))

ans = 1
stack = [(1, 0, graph[0])]

while stack:
    d, p, v = stack.pop()
    if ans < d: 
        ans = d
        if ans == 26:
            print(26)
            exit()
    
    i, j = p//C, p%C
    d += 1
    
    if (i+1) < R and not (w:=graph[k:=p+C])&v:
        stack.append((d, k, v|w))
    if 0 <= (i-1) and not (w:=graph[k:=p-C])&v:
        stack.append((d, k, v|w))
    if (j+1) < C and not (w:=graph[k:=p+1])&v:
        stack.append((d, k, v|w))
    if 0 <= (j-1) and not (w:=graph[k:=p-1])&v:
        stack.append((d, k, v|w))

print(ans)

 

예제 입력 1 

2 4
CAAB
ADCB

예제 출력 1 

3

예제 입력 2 

3 6
HFDFFB
AJHGDH
DGAGEH

예제 출력 2 

6

예제 입력 3 

5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

예제 출력 3 

10