[Python] 백준 1987번 - 알파벳

문제: https://www.acmicpc.net/problem/1987

1987번: 알파벳

문제를 보고 한 루트를 깊이 있게 팠다가 다른루트를 파기 때문에 가장먼저 DFS가 떠올랐다.

DFS대로 풀면서 백트래킹문제라는걸 알게되었다. 

 

처음에는 좌표에 대한 visited과 visited된 알파벳에 대해 각각 조회해주어야 한다고 생각했다.

그런데 생각해보니 어차피 4방향의 근접 알파벳 조회여부를 돌기때문에 좌표에 대한 visited는 따로 둘 필요가 없겠다는걸 알았다.

 

처음 제출했던 코드는 다음과 같다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
board = [list(input()) for _ in range(n)]
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
visited_letter = []
max_num = []

def dfs(x, y, cnt):
    global max_num
    max_num = max(cnt, max_num)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and board[nx][ny] not in visited_letter:
            visited_letter.append(board[nx][ny])
            dfs(nx, ny, cnt+1)
            visited_letter.pop()
    
visited_letter.append(board[0][0])
dfs(0, 0, 1)
print(max_num)

위의 코드로는 시간초과가 발생한다.

알고리즘자체는 백트래킹을 사용하여서 시간을 최소화했다고 생각했다.

예상가는 지점은 board[nx][ny] not in visited_letter 부분이었다.

해당 부분에서 리스트를 매번 돌면서 O(n)의 시간이 소요되기 때문이다.

답을 보고 힌트를 얻었던건 List 대신 Set을 이용해 풀이하는 방식이다.

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
board = [list(input()) for _ in range(n)]
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
visited_letter = set()
max_num = 0

def dfs(x, y, cnt):
    global max_num
    max_num = max(cnt, max_num)
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and board[nx][ny] not in visited_letter:
            visited_letter.add(board[nx][ny])
            dfs(nx, ny, cnt+1)
            visited_letter.remove(board[nx][ny])
    
visited_letter.add(board[0][0])
dfs(0, 0, 1)
print(max_num)

List만 Set으로 바꿔주어도 통과가 된다.

List에서의 in 조회는 O(n) 시간이 걸리는 반면 Set에서의 in 조회는 O(1)시간이 걸리기 때문이다.

 

+) PyPy와 sys.stdin.readline 조합이 더해져서 통과할 수 있었다. 

다른 풀이를 보니 bfs를 사용하면 python3를 사용하고도 통과할 수 있다고 한다.