[BOJ] 1987 알파벳 (Python3)

문제

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

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

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

입력

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

출력

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

정답 코드

r, c = map(int, input().split())
graph = [list(input()) for _ in range(r)]
log = set()
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
answer = 0

def dfs(x, y, count):
    global answer
    
    answer = max(answer, count)
    log.add(graph[x][y])
    
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        
        if 0 <= nx < r and 0 <= ny < c and graph[nx][ny] not in log:
            dfs(nx, ny, count + 1)
    log.remove(graph[x][y])
    
    
dfs(0, 0, 1)
print(answer)
    

3

문제풀이

보자마자 dfs문제라고 생각해서 바로 dfs로 풀이했는데 자꾸 시간초과가 나서, DP인가 하고 메모제이션도 사용해봤는데 아무리 생각해도 메모제이션으로 풀 수 없는 문제 같았다. 그래서 최대한 시간복잡도를 줄여보려고 노력하고 pypy3로 돌리니까 통과했다…

진짜 이런문제들 백준에서 퇴출시키면 안되나 ㅜ

그래도 이번 문제에서 새로운 사실을 알게 되었다.

a = 1
b = 2

위 코드보다,

a, b = 1, 2

가 시간복잡도가 더 적다는 사실을 알았다. 앞으로는 되도록이면 이렇게 변수 선언해야겠다.