[백준] 1987 알파벳 in Python : 백트래킹 + 시간초과 해결하기..

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

1987번: 알파벳

 

내가 바로 백트레킹이다 !!!! 하는 문제

dfs에서 경로에 현재 확인중인 array[nx][ny] 의 알파벳이 들어갈때 확인하고 다시 제거해서 원상복구한다 

그러나 시간 초과가 났다... 또륵 괜히 level.5 문제가 아니다 ㅎ 

ㅋㅋㅋ 왜맞틀? 왜시간초과?

# 1987 알파벳
r, c = map(int, input().split())
array = []
for _ in range(r):
    array.append(input())

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

count = 1
alphabet = []
def dfs(x, y, cnt):
    global count
    count = max(cnt, count)

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < r and 0 <= ny < c:
            if array[nx][ny] not in alphabet:
                alphabet.append(array[nx][ny])
                dfs(nx, ny, cnt+1)
                alphabet.remove(array[nx][ny])

alphabet.append(array[0][0])
dfs(0, 0, count)
print(count)

 

해결 방법 :

in 연산자는 선형탐색이므로 여기서 시간 복잡도를 줄여주어야 한다 

-> 알파벳을 26개의 칸으로 만들고 방문여부를 0, 1 로 구별한다 

# 1987 알파벳
import sys

r, c = map(int, sys.stdin.readline().split())
array = [list(map(lambda x:ord(x)-65, input().rstrip())) for _ in range(r)]

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

count = 1
alphabet = [0] * 26

def dfs(x, y, cnt):
    global count
    count = max(cnt, count)

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < r and 0 <= ny < c and alphabet[array[nx][ny]] != 1:
                alphabet[array[nx][ny]] = 1
                dfs(nx, ny, cnt+1)
                alphabet[array[nx][ny]] = 0

alphabet[array[0][0]] = 1

dfs(0, 0, count)
print(count)