💻 백준 1987번: 알파벳

문제 소개 🧐

R x C 크기의 보드에서, 같은 알파벳을 두 번 지나지 않으면서 말이 최대한 몇 칸을 지날 수 있는지 구하는 문제이다.

입력 📝

  • 첫째 줄에 R과 C가 주어진다. (1 ≤ R,C ≤ 20)
  • 둘째 줄부터 R개의 줄에 걸쳐 C개의 대문자 알파벳이 공백 없이 주어진다.

출력 📤

  • 말이 지날 수 있는 최대의 칸 수를 출력한다.

제한 ❌

  • 시간 제한: 2초
  • 메모리 제한: 256MB

첫 번째 시도: 단순 DFS

처음에는 간단한 DFS로 접근했다. 방문한 알파벳을 기록하면서 탐색하면 될 것이라고 생각했다.

import sys

R, C = map(int, sys.stdin.readline().split())
board = [list(sys.stdin.readline().rstrip()) for _ in range(R)]
move = [(-1, 0), (0, -1), (1, 0), (0, 1)] # 상 좌 하 우

def dfs(board, start: tuple[int, int]):
    global R, C
    global move

    visited_alphabet = [False] * 26
    stack = []
    stack.append(start)
    visited_alphabet[ord(board[start[0]][start[1]])-65]

    while stack:
        r, c = stack.pop()
        alpha = ord(board[r][c]) -65

        if visited_alphabet[alpha]:
            continue
        else:
            visited_alphabet[alpha] = True

        for dr, dc in move:
            next_r = r + dr
            next_c = c + dc

            if (next_r < 0 or next_r > R-1) or (next_c < 0 or next_c > C-1):
                continue
            
            stack.append((next_r, next_c))

    return visited_alphabet

visited_alpha = dfs(board, (0,0))
answer = 0
for i in range(26):
    answer += 1 if visited_alpha[i] else 0
print(answer)

결과는 실패였다. 😭

내 코드는 단순히 시작점에서부터 도달할 수 있는 모든 경로상의 알파벳 종류 수를 세는 것이었다. 문제의 요구사항인 ‘말이 이동한 최대 칸 수’, 즉 가장 긴 경로의 길이를 구하는 것과는 거리가 멀었다.

두 번째 시도: 백트래킹을 이용한 DFS

문제의 핵심은 ‘가장 긴 경로’를 찾는 것이므로, 한 경로로 끝까지 탐색한 뒤에는 다시 돌아와 다른 경로를 탐색해야 한다는 것을 깨달았다. 즉, 백트래킹(Backtracking) 이 필요한 문제였다.

DFS 탐색을 재귀적으로 구현하고, 재귀 호출이 끝날 때마다 방문했던 알파벳의 방문 표시를 해제하여 다른 탐색 경로에서 해당 알파벳을 다시 사용할 수 있도록 로직을 수정했다.

import sys
sys.setrecursionlimit(10000)

R, C = map(int, sys.stdin.readline().split())
board = [list(sys.stdin.readline().rstrip()) for _ in range(R)]
move = [(-1, 0), (0, -1), (1, 0), (0, 1)]  # 상 좌 하 우

visited = [False] * 26
answer = 0

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

    for dr, dc in move:
        nr, nc = r + dr, c + dc
        if 0 <= nr < R and 0 <= nc < C:
            alpha = ord(board[nr][nc]) - 65
            if not visited[alpha]:
                visited[alpha] = True
                dfs(nr, nc, depth + 1)
                visited[alpha] = False   # 백트래킹: 재귀 후 방문 표시 해제

# 시작점 방문 처리
visited[ord(board[0][0]) - 65] = True
dfs(0, 0, 1)

print(answer)

이 코드를 제출하니 Python3에서는 시간 초과가 발생했다. 하지만 PyPy3로 제출하니 성공적으로 통과할 수 있었다! 🎉

결론

‘알파벳’ 문제는 단순히 방문 가능한 노드를 찾는 것이 아니라, 특정 조건을 만족하는 ‘가장 긴 경로’를 찾는 문제이므로 백트래킹을 활용한 완전 탐색이 필수적이었다. 또한, Python의 재귀 깊이 제한과 실행 속도 문제로 인해 sys.setrecursionlimit 설정과 PyPy3 제출이 유효한 해결책이 되었다.

백트래킹의 개념을 다시 한번 확실히 다질 수 있었던 좋은 문제였다.