본문 바로가기
알고리즘

[알고리즘] 백준 13023 ABCDE

by 주주병 2024. 10. 16.
728x90
반응형

백준 13023 ABCDE

 

 

모든 시작점을 훑어야 하기 때문에 DFS문제라고 생각했다.
그러나 문제는 "어떻게 메모리를 줄여야 하냐?" 인 것이다.


      
import sys
def DFS(x,start):
if x == 4:
print(1)
sys.exit()
for i in range(n):
if f_ship[start][i] == 1 and res[i] == 0:
res[i] = 1
DFS(x+1,i)
res[i] = 0
n,m = map(int,sys.stdin.readline().split())
f_ship = [[0]*n for _ in range(n)]
for _ in range(m):
a,b = map(int,sys.stdin.readline().split())
f_ship[a][b] = 1
f_ship[b][a] = 1
res = [0]*n
for i in range(n):
res[i] = 1
DFS(0,i)
res[i] = 0
print(0)

📌 이렇게 했을 때 시간초과가 나왔다. 당연한 결과다 모든 경로를 보기 때문에 시간 복잡도는 O(N**4)가 나오기 때문이다. 문제의 시발점은 리스트를 초기화할 때 방문하지 않은 경로도 0으로 초기화 한 후 그 경로도 조사하는 것이다.

 


      
import sys
import collections
import heapq
def DFS(x,start):
if x == 4:
print(1)
sys.exit()
for i in f_ship[start]:
if res[i] == 0:
res[i] = 1
DFS(x+1,i)
res[i] = 0
n,m = map(int,sys.stdin.readline().split())
f_ship = [[] for _ in range(n)]
for _ in range(m):
a,b = map(int,sys.stdin.readline().split())
f_ship[a].append(b)
f_ship[b].append(a)
res = [0]*n
for i in range(n):
res[i] = 1
DFS(0,i)
res[i] = 0
print(0)

🔓 이렇게 처음부터 빈 리스트로 설정한 뒤 모든 경로를 입력할 때 f_ship[a][b] = 1 이렇게 체크하는 것이 아니라 f_ship[a].append(b)를 하는 것이 포인트다.

 

이렇게 하면 방문한 경로만 체크하기 때문에 시간낭비가 없어진다.

728x90
반응형