[Python/파이썬] 백준 1987번: 알파벳

문제

 

풀이

dfs + 백트래킹으로 풀었다.

pypy로 제출

중복된 문자를 체크하기 위해 alpha 배열 생성 (alpha[0] = True인 경우 A칸을 지났다는 의미)

alpha = [False] * 26

ord('A') - 65 이런 식으로 인덱스를 맞춰주었다.

그 후 백트래킹을 했다.

 

코드

import sys
input = sys.stdin.readline

r, c = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(r)]
alpha = [False] * 26
dir = ((0, 1), (0, -1), (1, 0), (-1, 0))
ans = 0

def condition(ni, nj):
    return ni < 0 or ni >= r or nj < 0 or nj >= c or alpha[ord(graph[ni][nj]) - 65]

def dfs(i, j, cnt):
    global ans
    ans = max(ans, cnt)
    
    for dx, dy in dir:
        ni, nj = i + dy, j + dx
        if condition(ni, nj):   continue
        alpha[ord(graph[ni][nj]) - 65] = True
        dfs(ni, nj, cnt + 1)
        alpha[ord(graph[ni][nj]) - 65] = False

alpha[ord(graph[0][0]) - 65] = True
dfs(0, 0, 1)
print(ans)

 

마무리

재귀는 너무 어렵다...