✅ BOJ 1987 - DFS, Backtracking, Bitmasking

BOJ 1987 알파벳

문제 핵심은 같은 알파벳 두 번 못 밟음. 시작 칸 포함해서 최대 몇 칸까지 갈 수 있냐 물어봄

접근

DFS+백트래킹. 좌표 방문 말고 알파벳 중복만 막으면 됨. 비트마스크로 처리. A~Z니까 26비트면 됨

비트마스크

visited | (1 << idx)로 방문 표시, visited & (1 << idx)로 이미 갔는지 확인. 리스트보다 빠름

DFS 흐름

지금 칸에서 상하좌우 돌려서 안 갔으면 depth+1 해서 재귀. visited는 새로 넘기니까 원복 필요 없음

시작

(0,0) 칸 알파벳으로 시작, depth=1부터 시작하면 됨

끝

 

#dfs,bitmasking,backtracking
import sys
input=sys.stdin.readline

def dfs(y,x,visited,depth):
    directions=[(1,0),(0,-1),(-1,0),(0,1)]
    global answer
    answer=max(answer,depth)
    
    for dy,dx in directions:
        ny=y+dy
        nx=x+dx
        #방문 가능한 범위에 속하고
        if 0<=ny<r and 0<=nx<c:
            idx=ord(grid[ny][nx])-ord('A')
            #방문했던 알파벳인 경우(전진불가)
            if visited & (1<<idx):
                continue
            #방문하지 않았던 알파벳인 경우(전진가능)
            dfs(ny,nx,visited|1<<idx,depth+1)

r,c=map(int,input().split())
grid=[]
for _ in range(r):
    grid.append(list(input().strip()))

visited=0
start_bit=ord(grid[0][0])-ord('A')
visited=(1<<start_bit)
        
answer=1
dfs(0,0,visited,1)
print(answer)