문제 링크: https://www.acmicpc.net/problem/1987

Thumbnail: Photo by Surendran MP (Unsplash)

그래프 탐색 문제입니다.

풀이

DFS

\(R \times C\) 크기의 격자에 임의의 알파벳들이 채워져 있습니다. \((0, 0)\)에서 탐색을 시작해, 한 번 지나간 알파벳을 다시 지나가지 않는 선에서 갈 수 있는 최대 길이를 구해야 하는 문제입니다.

DFS를 진행하면서, 방문 여부를 'A'부터 'Z'까지의 알파벳에 대해 검사하고, 만약 이번 재귀에서 더이상 탐색할 수 없다면 최대 길이를 갱신하는 방법으로 구현했습니다.

전체 코드

input = open(0).readline
R, C = map(int, input().split())
board = [list(input().rstrip()) for _ in range(R)]  # R x C 크기의 격자.

A_idx = ord('A')
visited = {chr(A_idx + i): False for i in range(26)} # 방문 여부를 검사할 Map

result = 0  # 가장 긴 경로의 길이
def dfs(y, x, distance = 1):
    next_dfs = 0
    for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        ny, nx = y + dy, x + dx
        if 0 <= ny < R and 0 <= nx < C:
            if not visited[board[ny][nx]]:
                next_dfs += 1
                visited[board[ny][nx]] = True
                dfs(ny, nx, distance + 1)
                visited[board[ny][nx]] = False
    if next_dfs == 0:  # 더 이상 갈 곳이 없는 경우.
        global result
        result = max(result, distance)

visited[board[0][0]] = True  # 시작 위치 방문 처리
dfs(0, 0)
print(result)  # 가장 긴 경로의 길이 출력