[백준] 1987번 알파벳 - Python / 알고리즘 중급 1/3 - 브루트 포스 - 재귀 (연습)

ByungJik_Oh·2025년 5월 7일

[Baekjoon Online Judge]

목록 보기

135/244

💡 문제

세로 $R$ 칸, 가로 $C$ 칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ( $1$ 행 $1$ 열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 $R$ 과 $C$ 가 빈칸을 사이에 두고 주어진다. ( $1 ≤ R,C ≤ 20$ ) 둘째 줄부터 $R$ 개의 줄에 걸쳐서 보드에 적혀 있는 $C$ 개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

💭 접근

이 문제에서 가장 중요한 조건으로 한번 지나온 알파벳을 다시 지나갈 수는 없다는 것이다.
따라서 각 칸을 지나가면서 이때까지 지나왔던 알파벳을 저장하고, 중복되는 알파벳 칸은 지나오지 않도록 해야한다. 이를 위해 ord() 함수를 사용하여 간단하게 저장할 수 있다.

visited[ord(alph[0][0]) - ord('A')] = True

이처럼 ord()함수를 사용하여 알파벳 A를 0으로, Z를 25로 인덱스를 가지는 visited 리스트에 A~Z를 지나온 적이 있는지 상태를 쉽게 저장할 수 있다.

이후, 위와 같은 방법으로 지나온 알파벳을 저장하면서 DFS를 호출하여 지날 수 있는 최대 칸을 구하면 된다.

📒 코드

def dfs(x, y, depth):
    global ans
    ans = max(ans, depth)

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # nx, ny가 범위를 벗어나지 않고, 지나온 적 없는 알파벳일 때
        if 0 <= nx < r and 0 <= ny < c and not visited[ord(alph[nx][ny]) - ord('A')]:
            visited[ord(alph[nx][ny]) - ord('A')] = True
            dfs(nx, ny, depth + 1)
            visited[ord(alph[nx][ny]) - ord('A')] = False

r, c = map(int, input().split())
visited = [False for _ in range(ord('Z') - ord('A') + 1)] # 이때까지 지나온 알파벳 저장
alph = [list(input()) for _ in range(r)]

ans = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited[ord(alph[0][0]) - ord('A')] = True
dfs(0, 0, 1)

print(ans)