백준 1987번

알파벳

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

문제

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

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

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

입력

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

출력

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

해설

이 문제는 주어진 보드에서 말이 지날 수 있는 최대의 칸 수를 구하는 문제입니다. 주요 제약은 같은 알파벳이 적힌 칸을 두 번 지날 수 없다는 것입니다.

이를 해결하기 위해 주어진 코드는 깊이 우선 탐색(DFS)을 사용하고 있습니다. 코드의 풀이 방법은 다음과 같습니다:

1. 방향 벡터 초기화: dx, dy는 말이 이동할 수 있는 네 방향(상, 하, 좌, 우)을 나타내는 방향 벡터입니다.
2. DFS 함수: dfs 함수는 현재 위치 (x, y)와 지금까지 지난 칸의 수 cnt를 인자로 받습니다. 함수 내에서는 현재 위치의 알파벳을 방문 처리한 후 주변 4 방향을 순회하면서 다음 칸으로 이동할 수 있는지 판단합니다.
3. 방문 판단: 만약 다음 칸이 보드의 범위를 벗어나거나, 이미 방문한 알파벳이라면 그 방향으로는 이동하지 않습니다.
4. 재귀 호출: 위의 조건을 만족하는 경우, 해당 위치로 이동하고 dfs 함수를 재귀적으로 호출합니다. 이 때, 지난 칸의 수는 1 증가시켜줍니다.
5. 백트래킹: 현재 위치에서 모든 방향을 탐색한 후에는 현재 위치의 알파벳의 방문 상태를 다시 되돌려줍니다. 이를 통해 다른 경로에서 해당 위치를 다시 방문할 수 있게 합니다.
6. 결과 출력: 모든 경로를 탐색한 후, 지날 수 있는 최대 칸 수를 출력합니다.

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y, cnt):
    global result
    result = max(result, cnt)
    alphabet = board[x][y]
    visited[ord(alphabet) - ord('A')] = True
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= r or ny >= c or visited[ord(board[nx][ny]) - ord('A')]:
            continue
        dfs(nx, ny, cnt+1)
    visited[ord(alphabet) - ord('A')] = False

r, c = map(int, input().split())
board = [input() for _ in range(r)]

visited = [False] * 26
visited[ord(board[0][0]) - ord('A')] = True
result = 1
dfs(0, 0, 1)

print(result)