[파이썬] [DFS] 백준 1987 알파벳

문제

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

1987번: 알파벳

코드

import sys
input=sys.stdin.readline

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

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

alpha=[0]*26
alpha[ord(array[0][0])-65]=1

result=0

def dfs(r,c,count):
    global result
    count+=1
    result=max(result,count)
    for i in range(4):
        nx=r+dx[i]
        ny=c+dy[i]
        if 0<=nx<R and 0<=ny<C:
            if not alpha[ord(array[nx][ny])-65]:
                alpha[ord(array[nx][ny])-65]=1
                dfs(nx,ny,count)
                alpha[ord(array[nx][ny])-65]=0

dfs(0,0,0)
print(result)

생각 정리

백트래킹을 이용해야 되는 문제 였다.