[백준] 1987번 알파벳 (Python 파이썬)(DFS)

www.acmicpc.net/problem/1987

1987번: 알파벳

문제 설명

R x C 크기의 보드판이 있다. 이 보드판의 각 칸에는 대문자 알파벳이 하나씩 적혀있으며, 이 보드판을 움직이는 말은 현재 (1,1)에 위치하고 있다. (시작점에 위치)

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있으며, 새로 이동하는 칸에 적힌 알파벳은 지금까지 지나온 알파벳과 겹쳐서는 안된다. 즉, 같은 알파벳 칸을 두 번 이상 지나갈 수 없다.

좌측 상단부터 시작하여 말이 최대 몇 칸을 지날 수 있는지를 출력하면 된다.

---

풀이 과정

이 문제는 DFS와 BFS 두 방법 모두 이용하여 풀어보았다. 먼저 이 오늘은 DFS로 푼 방법을 소개하려고 한다.

이 문제에서의 핵심은 DFS를 실행할 때는 가는 경로를 체크하면서 가다가 돌아올 때 다시 체크해제를 해주어야 한다. 

그래야 다른 경로들도 탐색하여 최댓값을 구할 수 있기 때문이다.

import sys

r, c = map(int, input().split())
graph = []
myStep = [0]*26
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
count = 0


def dfs(x, y, incnt):
    if x < 0 or x >= r or y < 0 or y >= c:
        return False
    global count
    count = max(incnt, count)

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if (0 <= nx < r and 0 <= ny < c) and not myStep[ord(graph[nx][ny]) - ord('A')]:
            myStep[ord(graph[nx][ny]) - ord('A')] = 1
            dfs(nx, ny, incnt + 1)
            myStep[ord(graph[nx][ny]) - ord('A')] = 0


for i in range(r):
    graph.append(list(sys.stdin.readline().strip()))
    
myStep[ord(graph[0][0]) - ord('A')] = 1
dfs(0, 0, 1)
print(count)

여기서, 사실 처음에는 myStep이라는 리스트에 알파벳들을 그대로 삽입하여 지나온 알파벳인지 검색하는 부분을

graph[nx][ny] not in myStep 로 이용하였다. 하지만 계속 시간초과가 발생하여 하나하나 고치다 보니 이 부분에서 시간초과 문제가 발생한 것을 깨달았고, 위의 코드처럼 myStep에 26칸(대문자 알파벳은 26개이므로)을 미리 만들어 준 후에, A를0으로 시작하여 Z까지 각 칸의 방문여부를 0, 1로 체크하도록 변경하였다. 그리고 통과할 수 있었다.

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !