[BOJ, Python] 1987번_알파벳

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기

백준 1987번

문제 설명을 보니 그래프 탐색 문제이고, 그 중에서도 깊이 우선 탐색(DFS) 문제라고 생각을 했다.
깊이 우선 탐색 문제의 경우 백트레킹을 같이 사용해주면 더 효율적으로 문제를 풀 수 있다.

1차 오답 코드 - 시간 초과

import sys
input = lambda: sys.stdin.readline().rstrip()

def dfs(r, c, count):
    global ans
    ans = max(ans, count)
    for x, y in d:
        rr,cc = r+x, c+y
        if promissing(rr, cc):
            alphas.add(maps[rr][cc])
            dfs(rr,cc, count+1)
            alphas.remove(maps[rr][cc])

def promissing(r, c):
    if 0<=r<R and 0<=c<C:
        if not maps[r][c] in alphas:
            return True
    return False

R, C = map(int, input().split())

maps = []
for i in range(R):
    maps.append(list(input()))

d = [[0,1], [1,0], [0,-1], [-1,0]]

alphas = set()
alphas.add(maps[0][0])

ans = 0
dfs(0,0,1)
print(ans)

DFS와 백트레킹을 이용해서 문제를 풀었다. alphas 집합을 만들어 지나간 알파벳을 담아주고, 백트레킹 함수인 primissing 함수에서 체크해준다.

반례와 예제 코드는 모두 통과를 했는데 코드를 제출하니 시간 초과가 발생했다.

백트레킹 과정을 별도의 promissing 함수로 만든 것이 원인일까?

2차 오답 코드 - 시간 초과

import sys
input = lambda: sys.stdin.readline().rstrip()

def dfs(r, c, count):
    global ans
    ans = max(ans, count)
    for x, y in d:
        rr,cc = r+x, c+y
        if 0 <= rr < R and 0 <= cc < C and maps[rr][cc] not in alphas:
            alphas.add(maps[rr][cc])
            dfs(rr,cc, count+1)
            alphas.remove(maps[rr][cc])

R, C = map(int, input().split())

maps = [list(input()) for _ in range(R)]

d = [(0, 1), (1, 0), (0, -1), (-1, 0)]

alphas = set(maps[0][0])
ans = 0
dfs(0,0,1)
print(ans)

시간 초과의 원인이 백트레킹 과정을 별도의 함수로 만든 것이 원인이라 생각해 제거했다.

1%에서 시간 초과 오류가 생기던 이전과 비교해서는 성능이 향상되기는 했지만 여전히 시간 초과가 발생한다.
내가 작성한 코드에 어떤 문제가 있는 걸까?
참고를 위해 다른 분들이 짠 코드를 참고했다. 대부분 나의 코드와 유사했는데 맹점은 다른 곳에 있었다.
파이썬의 경우 해당 문제를 해결하기 위해서는 Pypy3로 제출해야 한다는 것이다.

Pypy3로 제출한 결과

성공!
그러나 여전히 의문점은 남아있다. Python으로는 시간 초과 없이 해결할 수 있는 방법은 없는 걸까?
알고리즘 풀이에서의 Python의 한계를 알게 된 계기였다.