[알고리즘 분석 #4] 백준 1987 알파벳 ( 메모리 초과, 시간 초과, Python )

완전 미친놈임

미친것 같다.

문제 링크: https://www.acmicpc.net/problem/1987

시간초과 및 메모리 초과 해결법

1. 값을 빨리 찾는것은 List 의 In 은 O(n) SET은 O(1)

2. 재귀 횟수도 잘 고려해 보아야한다

만약 10**9로 하면 시간초과 난다

sys.setrecursionlimit(10000)

3. 처음에 visited 라는 방문 여부를 확인하는 배열을 넣어놨는데,  어차피 똑같은 알파벳이 있으면 돌아가지 못함으로 해당 배열을 빼도 된다.

 

코드

import sys
import time

sys.setrecursionlimit(10000)
input = sys.stdin.readline

n, m = map(int, input().split())
visit = set()

graph = list()
for _ in range(n):
    graph.append(list(input()))

visit.add(graph[0][0])

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

res = 0


def dfs(x, y, visit, cnt):
    global res

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < m and 0 <= ny < n:
            if graph[ny][nx] not in visit:
                visit.add(graph[ny][nx])
                res = max(res, cnt)
                dfs(nx, ny, visit, cnt + 1)
                visit.remove(graph[ny][nx])

    return cnt


dfs(0, 0, visit, 1)

print(res + 1)

 

set이랑 list랑 속도 차이

최악의 상황

20 20
AYXWVUTSRQPONMLKJIHG
YXWVUTSRQPONMLKJIHGF
XWVUTSRQPONMLKJIHGFE
WVUTSRQPONMLKJIHGFED
VUTSRQPONMLKJIHGFEDC
UTSRQPONMLKJIHGFEDCB
TSRQPONMLKJIHGFEDCBA
SRQPONMLKJIHGFEDCBAA
RQPONMLKJIHGFEDCBAAA
QPONMLKJIHGFEDCBAAAA
PONMLKJIHGFEDCBAAAAA
ONMLKJIHGFEDCBAAAAAA
NMLKJIHGFEDCBAAAAAAA
MLKJIHGFEDCBAAAAAAAA
LKJIHGFEDCBAAAAAAAAA
KJIHGFEDCBAAAAAAAAAA
JIHGFEDCBAAAAAAAAAAA
IHGFEDCBAAAAAAAAAAAA
HGFEDCBAAAAAAAAAAAAA
GFEDCBAAAAAAAAAAAAAA

답 : 25

1. set

2. list 의 in

약 16s 만큼이나 차이남