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

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

1987번: 알파벳

Problem

(0,0)에서 시작해서 조건에 맞게 말을 움직여보자.

조건

같은 알파벳을 2번 지날 수 없다.

SOL)

• 간단한 경로찾기 문제이다.
• BFS/DFS 어느것이든 가능할거 같다. DFS로 풀어보았다.
• DFS는 pypyp3로 통과가 되었고, BFS는 python3로도 통과가 되었다. 

import sys
input= sys.stdin.readline

R,C = map(int,input().split())
board = [list(input().rstrip()) for _ in range(R)]
alphabet=[False]*26
dist=0
dx=(1,0,-1,0)
dy=(0,1,0,-1)
def dfs(y,x,d):
    global dist
    dist= max(dist,d)
    
    for k in range(4):
        ny=y+dy[k]
        nx=x+dx[k]
        if 0<=ny<R and 0<=nx<C and not alphabet[ord(board[ny][nx])-65]:
            alphabet[ord(board[ny][nx])-65] = True
            dfs(ny,nx,d+1)
            alphabet[ord(board[ny][nx])-65] = False

alphabet[ord(board[0][0])-65] = True
dfs(0,0,1)
print(dist)