문제

입력

출력

문제풀이

• 처음에는 노드가 서로 순환하고 있는 것(원 모양)을 찾는 문제인 줄 알고, 방문노드(visited)에 들어 있는 노드는 건너뛰고, 없는 노드는 넣어서 지금 방문하고 있는 노드가 처음 방문한 노드와 일치하는지 확인하는 방식으로 접근하려고 했다.
• 깊이가 4인 그래프를 찾으라는 문제라는 것을 깨닫고 다음과 같은 방식으로 코드를 구현했다.
  
  
  
  

첫번째 코드 -> 시간초과

# ABCDE
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
relations = [[] for _ in range(n)]
answer = False

for i in range(m):
    x, y = map(int, input().split())
   
    relations[x].append(y)
    relations[y].append(x)

def dfs(now, cnt):
    global answer
  
    if cnt == 4:
        answer = True
        return
   
    visited.append(now)
    for i in relations[now]: 
        if i not in visited:
            dfs(i, cnt + 1)

for i in range(n):
    visited = []
    dfs(i,0)
   
if answer:
    print(1)
else:
    print(0)

시간초과 이유

• 성공한 코드와 비교했을 때, visited를 넣기만 하고 pop을 해주지 않아서 시간초과가 뜬 것 같다.

for i in relations[now]: 
        if i not in visited:
            dfs(i, cnt + 1)

visited를 pop을 해 주지 않으면 최대 1999개의 원소가 든 리스트를 순회하며 원소가 들어있는지 비교해야 하기 때문에 시간초과가 발생한 것 같다.

최종 코드 - 성공

# ABCDE
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
relations = [[] for _ in range(n)]
answer = False

for i in range(m):
    x, y = map(int, input().split())
   
    relations[x].append(y)
    relations[y].append(x)

def dfs(now, cnt):
    global answer
   
    if cnt == 4:
        answer = True
        return
  
    visited.append(now)
    for i in relations[now]: 
        if i not in visited:
            dfs(i, cnt + 1)
    visited.pop()

for i in range(n):
    visited = []
    dfs(i,0)
    if answer:
        break
   
if answer:
    print(1)
else:
    print(0)