파이썬 시간초과의 늪 (골드 4)

#1987번 알파벳 https://www.acmicpc.net/problem/1987

1987번: 알파벳

 

잘 짰다. 열심히 짰다.!...

틀린코드

r, c = map(int, input().split())

graph = [[ord(x)-65 for x in input()] for _ in range(r)]

# ord(alphabet) - 65 : A(idx = 0) ~ Z (idx = 25)
alpha = [False]*26
# print(ord("A")) : 65
# print(ord("Z")) : 90
# 26개

visited = [[False]*c for _ in range(r)]
dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]
answer = 0


def check(x, y):
    return 0 <= x < r and 0 <= y < c


def solve(position, alpha, length):
    global answer
    r, c = position
    if alpha[graph[r][c]]:
        answer = max(answer, length)
        return length

    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]
        if check(nr, nc) and not visited[nr][nc]:
            visited[nr][nc] = True
            alpha[graph[r][c]] = True
            solve([nr, nc], alpha, length+1)
            alpha[graph[r][c]] = False
            visited[nr][nc] = False


visited[0][0] = True
solve([0, 0], alpha, 0)

print(answer)

알파벳의 방문여부를 기록하는걸 조금 쉽게 진행하기 위해서 숫자형으로 변환해 인덱스별 논리값을 설정했다.

 

그런데 시간초과가 났다.

 

계속 이것저것 수정해봐도 시간초과가 났다.

아무래도 불필요한 연산이 많은 듯 하다.

 

정답코드 : 실행 pypy3

import sys
input = sys.stdin.readline

r, c = map(int, input().split())

graph = [[x for x in input()] for _ in range(r)]

alpha = set(graph[0][0])
dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]
answer = 0


def solve(x,y, length):
    global answer
    answer = max(answer, length)

    for i in range(4):
        nr = x + dr[i]
        nc = y + dc[i]
        if 0 <= nr < r and 0 <= nc < c and not graph[nr][nc] in alpha:
            alpha.add(graph[nr][nc])
            solve(nr, nc, length+1)
            alpha.remove(graph[nr][nc])


solve(0, 0, 1)

print(answer)

일단, 노드의 방문여부를 기록했던 visited 리스트를 지웠다. 알파벳 중복 여부만 판단해도 충분하기 때문이다.

 

나는 파이썬에서 in의 사용을 지양한다. 선형시간(O(n))이 소요되기 때문이다. 하지만 위 코드에서는 in을 사용했다. 탐색 데이터가 알파벳 수 만큼 고정되기 때문에 사용해도 영향이 적었던 듯 하다. 

내가 사용했던 방법인 알파벳 데이터를 정수형으로 변환하고, 이를 논리 리스트로 진행하는 것 보다 더 효율적이라는 사실이 놀라웠다.

 

* 백트래킹 (backtracking)

 : 노드를 탐색할 때, 해가 될 가능성을 판단한 후 유망하지 않다고 판단되면 노드의 이전 노드 (부모노드)로 돌아가는(backtracking) 탐색기법이다. 유망하지 않는 노드에 가는걸 가지치기(pruning)한다고 한다.

 

이 부분이 백트래킹이라고 보면 된다. 자식노드를 방문했던 기록을 지워줌으로써 구현할 수 있다.