[백준]13023 ABCDE dfs, 시간초과

풀이

일반적인 dfs문제인데 재귀를 타는 함수의 파라미터의 타입에 따라 시간초과가 발생하는 문제였다.

 

소스코드1 (시간초과)

dfs로 재귀가 들어갈때, visited라는 리스트를 파라미터로 쓰면 함수를 호출할때 계속 리스트를 달고 다녀야 한다

이 부분이 시간이 오래 걸린것으로 보인다

import sys
N,M = map(int,input().split())

graph={i:[] for i in range(N)}

for i in range(M):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

ans=0
def dfs(node,visited):
    global ans
    # print(node,visited)
    if sum(visited)==5:
        ans=1
        print(ans)
        sys.exit()
    else:
        for toNode in graph[node]:
            if visited[toNode]==0:
                visited[toNode]=1
                dfs(toNode,visited)
                visited[toNode]=0

for i in range(N):
    visited = [0 for _ in range(N)]
    visited[i]=1
    dfs(i,visited)
    if ans:
        break

print(ans)

 

소스코드2 (통과)

visited를 전역변수로 두고 int 타입의 cnt변수를 파라미터로 설정하여 해결

import sys
N,M = map(int,input().split())

graph={i:[] for i in range(N)}

for i in range(M):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

ans=0
visited = [0 for _ in range(N)]

def dfs(node,cnt):
    global ans
    # print(node,visited)
    if cnt==5:
        ans=1
        print(ans)
        sys.exit()
    else:
        for toNode in graph[node]:
            if visited[toNode]==0:
                visited[toNode]=1
                dfs(toNode,cnt+1)
                visited[toNode]=0

for i in range(N):
    visited[i] = 1
    dfs(i,1)
    visited[i] = 0
    if ans:
        break

print(ans)