백준 1987번 : 알파벳 in Python

1987번: 알파벳

 

www.acmicpc.net

이 문제는 각 칸에 대문자 알파벳이 하나씩 적혀 있는 R*C 크기의 보드가 있을 때 좌측 상단 칸에서 출발한 말이 지금까지 지나온 칸에 적힌 알파벳과 같은 알파벳이 적힌 칸을 지날 수 없을 때 최대 몇 칸을 지날 수 있는지를 구하는 문제이다.

이를 해결하기 위해서는 좌측 상단 칸에서 DFS를 시행하되, 현재까지 지나온 칸에 적힌 알파벳들을 따로 저장해둬 다음에 지날 칸에 적힌 알파벳이 이 알파벳 중 하나가 되지 않는 경우에만 해당 칸으로 진행하도록 함수를 작성한다. 그리고 백트래킹을 사용해 결과값을 반환하기 전에 현재 지난 칸에 해당하는 알파벳을 지워 후에 다른 경로를 통해 DFS를 시행할 때 정상적으로 해당 칸에 대한 방문을 할 수 있도록 한다.

이를 코드로 구현하면 다음과 같다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
# DFS 구현 함수에 추가 매개변수로 지금까지 지난 칸에 적힌 알파벳을 저장하는 문자열 letter을 추가한다.
def DFS(x, y, letter):
    global R, C
    # 지금까지 지난 칸에 적힌 알파벳 중 현재 방문한 칸에 적힌 알파벳이 있으면 return한다. 
    if board[x][y] in letter: return 0
    letter = letter + board[x][y]
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    # 현재 방문한 칸을 시작으로 할 때 최대 몇 칸을 지날 수 있는지를 저장하는 변수
    res = 1
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        if 0<=next_x<R and 0<=next_y<C and board[next_x][next_y] not in letter:
            # 상하좌우에 인접한 칸에 대해 DFS를 재귀적으로 호출한 결과 중 가장 큰 값에
            # 1을 더한 결과를 res로 한다.
            res = max(DFS(next_x, next_y, letter)+1, res)
    # 백트래킹
    letter = letter[:-1]
    return res
R, C = map(int, input().split())
board = []
for _ in range(R):
    board.append(input().strip())
print(DFS(0, 0, ""))