[백준/python]1987번 알파벳 - backtracking

보드를 방문하며 해당 보드를 방문한 적이 있는지, 해당 알파벳을 이미 마주친 적 있는 지만 확인해주면 된다. DFS를 이용한 백트래킹으로 간단하게 구현했다.

다른 풀이를 찾아보니 BFS로 푼 경우도 있고 시간초과가 나는 경우도 있는 것 같다. DFS와 백트래킹을 사용하지 않는다면 최단 거리 문제를 푸는 것처럼 BFS로 풀어도 되는 문제이다.

R, C = map(int, input().split())
board = [ [] for _ in range (R)]
for i in range(R):
    line = input()
    for j in range(C):
        board[i].append( ord(line[j])-65 )

visited=[[0 for _ in range(C)] for _ in range(R)]
checklist=[0 for _ in range(26)]

checklist[board[0][0]]=1
visited[0][0]=1

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

def DFS(x,y):
    global sol
    global tmp
    
    for i in range(4):
        nx,ny = x+dx[i], y+dy[i]
        
        if 0<=nx<R and 0<=ny<C :
            alphabet = board[nx][ny]
            if visited[nx][ny]==0  :
                if checklist[alphabet]==0:
                    visited[nx][ny]=1
                    checklist[alphabet]=1
                    tmp+=1
                    DFS(nx,ny)
                    tmp-=1
                    checklist[alphabet]=0
                    visited[nx][ny]=0
    
    sol = max(sol, tmp)
    return

DFS(0,0)
print(sol)

구현

1. 알파벳의 방문 표시를 간단하게 수행하기 위해 아스키코드 표를 참조하여 정수형태로 변환한다.
2. 보드를 방문한 적이 있는지 visited 배열에 표시하고 checklist에는 방문한 알파벳을 표시한다.
3. tmp에 한 칸씩 나아갈 때마다 이동횟수를 추가한다.