[골드 4] 백준 1987 - 알파벳 (파이썬)

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

풀이

• R행 C열의 보드가 주어짐.
• 보드의 각 칸에는 알파벳 대문자가 하나씩 있음.
• (0, 0)부터 시작하여 상하좌우로 이동.
• 같은 알파벳을 두 번 지나갈 수 없음.
• 최대로 이동할 수 있는 칸 수 출력.

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

R * C 크기의 보드를 입력받는다.

answer = 0
check = [False] * 26

check 배열은 A ~ Z 26개의 알파벳 사용 여부를 기록한다.

def dfs(r, c, count) :
    global answer
    answer = max(answer, count)

현재 위치까지 이동한 칸 수 count를 이용해 answer를 갱신한다.

for i in range(4) :
    nr, nc = r + dr[i], c + dc[i]
    if nr < 0 or R <= nr or nc < 0 or C <= nc :
        continue

범위를 벗어나는 위치는 무시한다.

if check[ord(B[nr][nc]) - ord('A')] :
    continue

이미 사용한 알파벳이면 탐색하지 않는다.

check[ord(B[nr][nc]) - ord('A')] = True
dfs(nr, nc, count + 1)
check[ord(B[nr][nc]) - ord('A')] = False

백트래킹을 이용해서 방문 했다가 돌아올 때 다시 False로 바꿔준다.

check[ord(B[0][0]) - ord('A')] = True
dfs(0, 0, 1)
print(answer)

(0, 0) 위치의 알파벳 사용 표시 후 DFS를 시작한다.

코드

# 백준 1987 - 알파벳
# 분류 : 브루트포스

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

answer = 0
check = [False] * 26

dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]

def dfs(r, c, count) :
    global answer
    answer = max(answer, count)

    for i in range(4) :
        nr, nc = r + dr[i], c + dc[i]
        if nr < 0 or R <= nr or nc < 0 or C <= nc :
            continue

        if check[ord(B[nr][nc]) - ord('A')] :
            continue
        
        check[ord(B[nr][nc]) - ord('A')] = True
        dfs(nr, nc, count + 1)
        check[ord(B[nr][nc]) - ord('A')] = False

check[ord(B[0][0]) - ord('A')] = True
dfs(0, 0, 1)
print(answer)