[dfs/백준] 13023번 : ABCDE

- 문제 : https://www.acmicpc.net/problem/13023

 

깊이가 4인 노드를 찾는 문제라고 생각한 후 그렇게 작성해봤는데, 생각보다 쉽지 않았던 문제 

탐색을 진행한 다음에 visit를 왜 0 처리 하는지 모르겠다 

 

- 정답 풀이 :

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline

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

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

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

def dfs(v,depth): 
    global flag
    visit[v]=1
    if depth==4:
        flag=True
        return flag
    for x in data[v]:
        if not visit[x]:
            dfs(x,depth+1) 
            visit[x]=0 #여기
    return False   

flag=False
visit=[0]*n #여기           
for i in range(n):
    dfs(i,0)
    visit[i]=0 #여기
    if flag:
        break
if flag:
    print(1)
else:
    print(0)