백준 #1987 - [G4] 알파벳 : 백트래킹, 시간초과

(python3)

1987번: 알파벳

 

백트래킹

전형적인 dfs 백트래킹으로 해결할 수 있습니다. 매번 4방향으로 재귀를 돌고, 들렀던 알파벳을 만나면 끝내는 방식으로 적용합니다.

 

시간초과

이미 들렀던 알파벳을 어떻게 확인할것인가? 부분에서 어떤 방식과 자료구조를 취하느냐에 따라 시간초과가 발생할 수 있습니다. 저는 3가지 방식을 적용해봤습니다.

 

1. deque : 들렀던 알파벳을 deque 에 append 하고, 백트래킹에서 빠져나올때 pop 하는 형식. in 으로 들렀던 알파벳인지 탐색합니다. list in 시간복잡도 O(N) : 시간초과

2. set : 들렀던 알파벳을 set 에 add 하고, 빠져나올때 remove. in 으로 들렀던 알파벳인지 탐색합니다. set in 시간복잡도 이론상 O(1) : 시간초과

3. list : 알파벳 A~Z 를 대변하는 배열을 만들고 들렀던 알파벳의 flag = 1 로 표시하는 방식. 인덱스 접근으로 들렀던 알파벳인지 확인합니다. 시간복잡도 O(1) : 성공

 

이때 set 의 시간복잡도는 이론상 O(1) 이긴 하지만, 해시 자료구조는 기본적으로 해시펑션 연산을 진행해야하기 때문에 자료구조 자체가 무겁습니다. 이러한 이유로 채점 중간쯤 시간초과가 발생합니다.

 

코드

import sys
def solution(input) : 
    # 입력받기
    R,C = list(map(int,input().split()))
    M = []
    for _ in range(R) :
        M.append(input().strip())
    # A~Z 중 들른 알파벳 체크
    check_list = [0] * 26
    # 알파벳 to list index
    def alph_to_asci(a) :
        return ord(a)-ord('A')
    # 4방향
    D = [(-1,0),(1,0),(0,-1),(0,1)]

    # 백트래킹
    def backtrack(r,c,check_list,cnt,maxcnt) :
        k = alph_to_asci(M[r][c])
        if check_list[k] : # 들렀던 알파벳이면 종료
            maxcnt = max(cnt,maxcnt)
            return maxcnt
        
        check_list[k] = 1
        cnt+=1
        for dr,dc in D :
            nr = r+dr
            nc = c+dc
            if nr>=0 and nr<R and nc>=0 and nc<C :
                maxcnt = backtrack(nr,nc,check_list,cnt,maxcnt)
        check_list[k] = 0
        return maxcnt
    
    print(backtrack(0,0,check_list,0,0))

input = sys.stdin.readline
solution(input)

 

my solved.ac :

solved.ac