[백준 1987] 알파벳

문제

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

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

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

 

입력

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

 

출력

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

---

접근

DFS로 가능한 모든 경로의 수를 탐색하여 최댓값을 찾는다.

탐색할 때마다 최댓값 비교를 진행한다.

 

계속해서 BFS로 풀었는데 테스트 케이스는 맞지만 틀렸다고 나왔다. 아직 어디서 틀린지 알지 못했다.

그래서 DFS로 풀었고 시간초과가 발생해서 PYPY3로 제출을 했다.

 

구현

현재 위치에서 상하좌우 탐색을 진행하고, 갈 수 있으면 재귀호출을 진행한다.

visited은 26개의 False로 초기화되어있으며 각 알파벳이 이전에 방문했는지 여부를 체크한다.

def dfs(y, x, count):
    global answer
    answer = max(answer, count)

    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]
        if check_range(ny, nx) and not visited[board[ny][nx]]:
            visited[board[ny][nx]] = True
            dfs(ny, nx, count+1)
            visited[board[ny][nx]] = False

---

전체 코드

import sys
from _collections import deque
input = sys.stdin.readline

def check_range(y, x):
    return (y>=0 and y<R) and (x>=0 and x<C)

def dfs(y, x, count):
    global answer
    answer = max(answer, count)

    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]
        if check_range(ny, nx) and not visited[board[ny][nx]]:
            visited[board[ny][nx]] = True
            dfs(ny, nx, count+1)
            visited[board[ny][nx]] = False

R, C = map(int, input().split())
board = [list(map(lambda x:ord(x)-65, input().strip())) for _ in range(R)]
answer = 0
visited = [False] * 26
visited[board[0][0]] = True
dfs(0, 0, 1)
print(answer)