[백준] 13023문제 (ABCDE) 파이썬(Python) 풀이

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

13023번: ABCDE

import sys
input = sys.stdin.readline

finshed = False
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
visited = [False] * n

for _ in range(m):
    v1, v2 = map(int, input().split())
    graph[v1].append(v2)
    graph[v2].append(v1)

def dfs(start, depth):
    global finshed
    visited[start] = True

    if depth == 4:
        finshed = True
        return
    for i in graph[start]:
        if not visited[i]:
            dfs(i, depth + 1)
            visited[i] = False

for i in range(n):
    dfs(i, 0)
    visited[i] = False
    if finshed:
        break

print(1 if finshed else 0)

문제 지문이 무엇을 말하는지 이해를 못 했는데, 알고보니 그래프의 깊이(depth)를 구하는 문제였다.

결과적으로 문제의 포인트는 주어진 그래프의 깊이가 4 이상이냐, 아니냐를 묻는 문제였다.

 

4 이상이면 1을 출력,

아니면 0을 출력한다.

 

전형적인 깊이 우선 탐색(dfs)을 통해 그래프를 탐색하며 depth를 더해가며 풀 수 있다.