백준 1987 파이썬 코드 답안

 

 

 

문제

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

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

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

입력

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

출력

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

 

문제 풀이

기본적으로 해당 문제는 BFS와 DFS만으로는 시간 초과로 인해 추가적인 테크닉이 필요하다. 바로 백트래킹 기법이 들어가야한다. 여기서 백트래킹 기법은 불가능한 상황인 것을 인지했을 때, 그쪽으로 더 탐색하지 않고 돌아오는 것으로 이해를 하면 된다.

여기서 유망한 노드를 확인하는 조건은 다음과 같다.

1. 다음에 지나갈 x,y 좌표가 범위를 벗어나지 않는다.
2. 다음에 지나갈 위치에 있는 문자가 쓰이지 않는다.

1은 BFS를 사용할 때 너무 많이 쓰이는 조건이므로 쉽게 표현할 수 있으나, 2번은 새로운 리스트를 하나 만들어 관리한다. 나는 처음에 2번을 위해서 딕셔너리를 만들어서 사용을 했으나, 딕셔너리를 사용한 코드로는 항상 시간 초과가 발생했다. 다른 분들의 댓글을 확인해보니, 딕셔너리에서 뭔가를 구현하게 될 경우 BEST는 O(1)의 시간복잡도이지만 Worst일 경우에는 O(n)이 된다고 한다. 

따라서, 문자를 잘 표현하기 위해서 아스키코드 (ord[문자])를 사용해서, 리스트로 가장 빠르게 구현하도록 하니 코드가 통과되었다. 

 

 

import sys
def dfs(y,x,cnt) :
    global answer
    answer = max(answer,cnt)
    for h in tra_list :
        next_y = y + h[0]
        next_x = x + h[1]
        if 0 < next_y < r+1 and 0 < next_x < c+1 :
            if d[ord(my_map[next_y][next_x])-65] == 0 :
                d[ord(my_map[next_y][next_x])-65] = 1
                cnt +=1
                dfs(next_y,next_x,cnt)
                d[ord(my_map[next_y][next_x])-65] = 0
                cnt -=1



tra_list = [[1,0],[0,1], [-1,0], [0,-1]]
d = [0 for _ in range(26)]
r,c = map(int,sys.stdin.readline().split())
my_map = [[0] for _ in range(r+1)]
for i in range(1,r+1) :
    temp = str(sys.stdin.readline().rstrip())
    for k in temp :
        my_map[i].append(k)

answer = 0
d[ord(my_map[1][1])-65] = 1
dfs(1,1,1)
print(answer)