백준 1987번: 알파벳 (파이썬)

https://www.acmicpc.net/problem/1987

1987번: 알파벳

 

문제

 

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

 

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

 

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

 

입력

 

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

 

출력

 

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

 

풀이

 

알파벳을 아스키코드로 변환하여 방문한 것과 방문하지 않은 것을 구분하였다.

이후 DFS에서 최장거리 문제를 푸는 것과 동일하게 해결하였다.

그런데 Python 3로 제출했을 때는 시간초과 문제가 발생하였고, PyPy3로 제출하자 통과되었다.

이전에도 비슷한 경험이 있었는데, 추후에 그 문제와 함께 이 문제를 다시 해결해 볼 것이다.

 

소스 코드

 

r, c = list(map(int, input().split()))

board = []
dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for _ in range(r):
    board.append(input())

visited = [False for _ in range(26)]
DIFF = ord('A')
def dfs(x, y):
    global visited

    asc = ord(board[x][y])
    visited[asc-DIFF] = True
    cnt = 1

    local_max_cnt = 0
    for dx, dy in dxy:
        if x+dx < 0 or x+dx >= r or y+dy < 0 or y+dy >= c:
            continue
        _asc = ord(board[x+dx][y+dy])
        if not visited[_asc-DIFF]:
            visited[_asc-DIFF] = True
            local_cnt = dfs(x+dx, y+dy)
            local_max_cnt = local_cnt if local_cnt > local_max_cnt else local_max_cnt
            visited[_asc-DIFF] = False

    cnt += local_max_cnt
    return cnt

print(dfs(0, 0))