[BOJ]13023 - ABCDE (Python)

문제 

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

코드 

import sys
input = lambda: sys.stdin.readline().strip()


def dfs(v, depth):
    global ans
    visited[v] = 1
    if depth == 4:
        ans = True
        return
    for i in graph[v]:
        if visited[i] == 0:
            dfs(i, depth + 1)
            visited[i] = 0


N, M = map(int, input().split())
graph = [[] for _ in range(N)]
visited = [0 for _ in range(N)]
ans = False

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

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

print(1 if ans else 0)

 

풀이

문제 이해를 잘못해서 초반에 접근이 어려웠다

질문글에서 `depth` 힌트를 보게 되었고 그래프의 깊이를 사용해서 문제를 풀 수 있었다 

기존에는 graph 이중 리스트에 노드들이 연결 되어있는지(1) 아닌지(0) 저장했었는데 이 문제에서는 시간 초과가 계속 났었다 

그래서 그냥 입력받은 노드들을 인덱스로 해서 연결되어 있는 노드를 해당 자리에 넣었다 

이 문제를 통해서 배운 점... 

 

• 그래프 문제들은 깊이를 생각해야 되는 문제가 나올 수 있으니 항상 염두해두기 
• 그래프(리스트) 자체에 값을 넣어보기 
• dfs 함수 한 번 돌때마다 깊이 증가시켜주기