[백준] 1987 알파벳 (파이썬), 시간 초과 해결하는 법

막대한 시간 차이를 볼 수 있다.

def dfs(graph, v, already, depth):
    global ans
    # visited랑 알파벳의 already랑 겹치기 때문에 필요 없음

    r, c = v
    stack = set()
    stack.add((r, c, already+graph[r][c], depth))

    while stack:
        nowr, nowc, nowalready, nowdepth = stack.pop()
        ans = max(ans, nowdepth)
        for i in range(4):
            newr, newc = nowr+dr[i], nowc+dc[i]
            if 0 <= newr < R and 0 <= newc < C and graph[newr][newc] not in nowalready:
                stack.add((newr, newc, nowalready + graph[newr][newc], nowdepth+1))
    return

R, C = map(int, input().split())
graph = [list(input()) for _ in range(R)]

ans = 0
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

dfs(graph, (0, 0), '', 1)

print(ans)

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

1987번: 알파벳

 

풀이 자체는 평범한 dfs로 풀어도 된다. bfs로는 파이썬으로 제출 가능하고 dfs로는 pypy로만 제출 가능한 듯하다. 하지만 안정적인 풀이를 위해서는 조금 더 근본적인 변화가 필요하다.

20 20
ABCDEFGHIJKLMNOPQRST
BCDEFGHIJKLMNOPQRSTU
CDEFGHIJKLMNOPQRSTUV
DEFGHIJKLMNOPQRSTUVW
EFGHIJKLMNOPQRSTUVWX
FGHIJKLMNOPQRSTUVWXY
GHIJKLMNOPQRSTUVWXYZ
HIJKLMNOPQRSTUVWXYZA
IJKLMNOPQRSTUVWXYZAA
JKLMNOPQRSTUVWXYZAAA
KLMNOPQRSTUVWXYZAAAA
LMNOPQRSTUVWXYZAAAAA
MNOPQRSTUVWXYZAAAAAA
NOPQRSTUVWXYZAAAAAAA
OPQRSTUVWXYZAAAAAAAA

위와 같은 극단적인 예시를 생각해보자. 20, 20을 꽉 채웠고 겹치는 글자 없이 경로를 이어나갈 수 있는 길이 대충 봐도 많아보인다.

따라서 dp와 같이 중간중간 저장할 수 있는 방식을 생각해야 한다. 위는 좌상단을 확대한 그림이다. A 경로로 row=4, col=4에 도착하든 B 경로로 도착하든 기존에 밟아왔던 알파벳, 현재 위치, 앞으로 갈 수 있는 위치 모두 동일하다. 일반적인 dfs로는 이런 경우를 고려하지 못하고 동일한 작업을 2번할 것이다.

(1동일좌표, 동일과거), (2다른좌표,동일과거), (3동일좌표, 다른과거), (4다른좌표,다른과거) 에 대해서 일반적인 그래프 문제는 13<->24이기 때문에 좌표만 visited_coordinates에 저장하면 됐었다. 하지만 이번에는 1<->234이기 때문에 visited_coordinates, visited_alphabets 모두 필요하다. row, col, 기존 경로를 모두 저장하는 건 row20*col20*알파벳A포함여부2*알파벳B포함여부2.....총 400*2^26차원의 행렬을 생성할 수도 있겠으나 어차피 dfs든 bfs든 array 내에서 구현이 되기 때문에 이 array 자체를 dp로 사용하도록 하자.

파이썬의 set는 내부적으로 dictionary처럼 된다고는 하는데 list, deque처럼 pop이 있다. 이걸 쓰자. 요소의 unique함을 보장하기 때문에 set를 사용하면 된다.
(여기서 지나온 경로를 저장하는 변수 alpha, currently_visited, already의 type은 str이다. set로 변경하는 것은 바깥 set가 안의 set를 hashable 하지 못하기 때문에 불가능하다. ord와 list를 이용해 길이 26짜리 list를 쓰는 건 가능하고 str보다는 성능이 조금 더 오를 듯하다.)
(행렬로 구현하는 것과 달리 이 구현에서는 중복되는 경우의 수 1이 이미 array에서 빠져나갔다면 경우의 수 2는 걸러내지 못하고 중복 계산하는 경우도 있다. 또한 set.pop()은 랜덤하게 요소를 반환한다. 따라서 깊이탐색, 넓이탐색이 아닌 그 중간의 무언가라고 봐야한다. A* 알고리즘에서 휴리스틱을 rand로 한다면 이것과 비슷하다. 아무튼 이 2가지 요소가 겹쳐져서 중복 계산을 못 걸러낸 총 횟수는 시행마다 매번 달라지게 된다. 참고로 위에 적은 예시에서는 약 50% 가량을 걸러낸다. 다른 문제에서는 2가지 요소 모두 조심해야 될 듯하다.)

# 수정 전
from collections import deque

def bfs(original, x, y):
    max_len = 1
    q = deque([(x, y, original[y][x])])
    while q:
        x, y, alpha = q.popleft()
        max_len = max(max_len, len(alpha))
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < c and 0 <= ny < r and original[ny][nx] not in alpha:
                q.append((nx, ny, alpha + original[ny][nx]))

    return max_len

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

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

print(bfs(original, 0, 0))

# 수정 후
from collections import deque

def bfs(original, x, y):
    max_len = 1
    q = set([(x, y, original[y][x])])  # set로 변경
    while q:
        x, y, alpha = q.pop()  # pop으로 변경
        max_len = max(max_len, len(alpha))
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < c and 0 <= ny < r and original[ny][nx] not in alpha:
                q.add((nx, ny, alpha + original[ny][nx]))  # add로 변경
    return max_len

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

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

print(bfs(original, 0, 0))

수정 전은 https://www.acmicpc.net/board/view/100600 시간 초과의 이유를 묻는 질문 글이다. 나와 비슷하게 수정을 하여서 성공하였지만 이유를 알지 못한 질문 글, https://www.acmicpc.net/board/view/82024 도 있다. 위와 같이 간단하게 수정하면 시간 초과를 해결할 수 있다.

def dfs(x, y):
    global board, R, C

    max_depth = 0
    queue = set() # 주의
    queue.add((x, y, board[y][x]))
    while queue: # 주의
        current_x, current_y, current_visited = queue.pop()
        max_depth = max(max_depth, len(current_visited))
        if max_depth == 26:
            return 26
        for movement in movement_array:
            next_x = current_x + movement[0]
            next_y = current_y + movement[1]
            if 0 <= next_x < C and 0 <= next_y < R and board[next_y][next_x] not in current_visited:
                queue.add((next_x, next_y, current_visited + board[next_y][next_x]))
    return max_depth

이 https://www.acmicpc.net/source/21647170 처럼 dfs를 재귀가 아닌 stack(set을 사용한)으로 구현하여도 된다.

 

다른 풀이도 있다. "400*2^26차원의 행렬을 생성할 수도 있겠으나 어차피 dfs든 bfs든 array 내에서 구현이 되기 때문에 이 array 자체를 dp로 사용하도록 하자."이 아닌 평소처럼 visited를 만들되 타입을 set로 만드는 것이다. 메모리는 3배 정도 늘고 속도는 비슷하다. 총 탐색 경우의 수가 매우 줄고(정작 속도는 비슷하다) 랜덤성에 의존하지 않는다. 가장 큰 장점은 구현을 떠올리기 쉽다는 것. 이 방식이 훨씬 나을 듯하다.