[BOJ 1987 파이썬] 알파벳 백트래킹 DFS

1987번: 알파벳

문제

---

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

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

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

입력

---

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

출력

---

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

예제 입력 1 

2 4
CAAB
ADCB

예제 출력 1 

3

예제 입력 2 

3 6
HFDFFB
AJHGDH
DGAGEH

예제 출력 2 

6

예제 입력 3 

5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

예제 출력 3 

10

 

일단 문제를 보자마자 그래프 탐색 이라는 생각이 들어야하고, 무작정 그래프 모양대로 visited 배열을 만들고 DFS를 돌리며, 문자열에 다음 탐색할 문자가 있는지 탐색하기 위해 in을 사용한다면 시간 초과의 문제에 직면하게 될 것이다.

 

문제에 따라 다르겠지만, 반복문 (본 문제의 경우 재귀함수) 안에 in을 사용하여 리스트 혹은 문자열 안에 해당 아이템이 있는지 판단하는 것은 O(n^2)의 시간이 걸리기 때문에 최대한 자제해야한다.

 

이번 문제의 경우 계속 문자열을 in을 사용해서 체크할 경우 O(n!)의 시간복잡도(문자열 길이가 1일때 한번 2일때 한번 쭉 계속 비교하기 때문에)가 경로마다 걸리기 때문에 DFS의 시간복잡도 * O(n!)의 시간복잡도가 걸려 어마어마하게 많은 시간이 걸리게 된다.

 

이제 이것을 알게 되었다면 다른 방법을 찾아야하는데, 이를 생각하기가 굉장히 어려운 문제였다.

 

visited 배열을 사용하는 것에 너무 익숙해져 있어서, 다른 방법을 생각해내기 쉽지 않을텐데

 

이 방법은 바로 visited 배열이 아닌 A~Z의 문자열 배열을 이용하는 방법이다.

 

즉, A~Z의 문자열 배열에서 한번 방문한 문자의 경우 True로 만들어주고 그곳을 방문 했다면 문자열의 길이를 비교하여 최대 길이를 가진 문자열의 길이를 반환해주면 된다.

 

자세한 사항은 코드!!

import sys

R,C = map(int,sys.stdin.readline().rstrip().split())

board = [list(sys.stdin.readline().rstrip()) for _ in range(R)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
alphabet =[False for i in range(26)]
alphabet[ord(board[0][0])-65] = True
result = 0

def dfs(x,y,al,depth):
    global result

    result = max(result,depth)
   
    for i in range(0,4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >=0 and ny >=0 and nx < C and ny < R:
            if not al[ord(board[ny][nx])-65]:
                al[ord(board[ny][nx])-65] = True     
                
                dfs(nx,ny,al,depth+1)
                al[ord(board[ny][nx])-65] = False        

            

dfs(0,0,alphabet,1)

print(result)

 

발상의 전환이 어려웠던 문제다...😂

생각의 전환 뿐만 아니라 dfs를 통해  그래프 탐색에 굉장히 익숙해져있었어야 풀 수 있었던 문제 같다.✔

 

코드에 대한 질문이나 이견은 언제나 댓글 주세요!