[Python(PyPy)] 백준 1987번 - 알파벳 (골드 4)

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 깊이 우선 탐색(DFS)
 - 백트래킹

 

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

1987번: 알파벳

 

문제

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

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

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

입력

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

출력

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

 

 

---

 

(0, 0) 지점부터 중복되지 않은 알파벳을 최대로 가져오는 값을 구하는 문제이다.

 

import sys
input = sys.stdin.readline

r, c = map(int, input().split())
data = []
for _ in range(r):
    data.append(list(input().rstrip()))
    
AtoZ = [0] * 26
#A - 65, Z - 90 Ascii Code

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def dfs(x, y, tmp):
    global result
    result = max(result, tmp)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < r and 0 <= ny < c:
            ch = data[nx][ny]
            idx = ord(ch)-65
            if AtoZ[idx] == 0:
                AtoZ[idx] = 1
                dfs(nx, ny, tmp+1)
                AtoZ[idx] = 0

ch = data[0][0]
idx = ord(ch)-65
AtoZ[idx] = 1
result = 1
dfs(0, 0, 1)
print(result)

 

A~Z값을 ASCII코드로 구하여 0~26의 배열을 각 알파벳으로 위치한다.

 

AtoZ 배열이 기존의 visited 배열을 대신하는 것이다.