[백준] 1987 : 알파벳 - Python

문제

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

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

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

입력

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

출력

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

import sys
sys.stdin = open("input.text", "rt")
input = sys.stdin.readline
sys.setrecursionlimit(10000)

r, c = map(int, input().split())
g = []
for _ in range(r):
    temp = list(input())
    g.append(temp)

dx = [1,-1,0,0]
dy = [0,0,1,-1]

ch = [False] * 26 #시간초과 떄문에 방문표시를 이렇게...
max_cnt = -2424242424
def DFS(x,y,cnt):
    global max_cnt
    max_cnt = max(max_cnt , cnt)

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<r and 0<=ny<c:
            if ch[ord(g[nx][ny]) - 65] == False: #아직 방문 전
                ch[ord(g[nx][ny]) - 65] = True
                DFS(nx,ny,cnt + 1)
                ch[ord(g[nx][ny]) - 65] = False
        

ch[ord(g[0][0]) - 65] = True #시작점은 방문표시하고 들어가야함
DFS(0,0,1)
print(max_cnt)
    

코멘트

DFS로 풀었는데 python3으로 제출하면 시간초과가 뜬다. 그리고 처음에 체크리스트를 만들지 않고 res라는 리스트안에 문자열을 계속 더해나갔다 이것 때문에 계속 오류가 떳는데.. 알파벳 크기만큼 True/False로 만들어줘서 체크리스트를 만들어주니 해결됐다... 코테에서 시간초과 이렇게 잡을지 걱정된다.

보자마자 한 곳만 쭉 파는 형식으로 해야겠구나 싶어서 DFS를 생각했는데 코드 짜다 보니까 BFS로 해도 해결될 것 같다.

• 백트랙킹 과정에서 체크 리스트 풀어주는거 잊지말자!