[DFS/BFS] 백준 - 13023번 ABCDE

문제 링크

😊 문제 요약

a-b-c-d-e처럼 총 5개가 연결되어있는지 확인하라!! 연결되어 있다면 1, 연결되어 있지 않으면 0을 출력하라!

😂 key point!!

깊이 우선 탐색이나 너비 우선 탐색으로 노드들의 depth(깊이)를 구할 수 있어야 한다.
필자는 dfs를 이용하여 count변수를 통해 노드들의 깊이를 파악하였다.

n,m = map(int, input().split())

graph = [[] for _ in range(n)]

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

# 깊이를 나타내는 count == 4인 것을 나타내기 위한 전역 변수
check = [0] 

def dfs(graph,v,visited,count):
    
    visited[v] = True
    
    if count == 4:
        check[0] = 1 
        return 
    
    for i in graph[v]:
        if visited[i] == False:
            dfs(graph,i,visited,count+1)
            visited[i] = False        #노드의 다른 길 방문을 위해 리셋

result = 0

visited = [False] * n

for i in range(n):
    visited[i] = [False]              #방문기록을 나타내는 visited 리셋
    dfs(graph,i,visited,0)
    if check[0] == 1:
        result = 1
        break

if result == 1:
    print(1)
else:
    print(0)