[Python/백준]ABCDE(DFS)

 

 

 

 

 

 

 

유니온 파인드인줄 알았는데 아니었다.  DFS 였다. 

그저 A,B,C,D,E 가 각각 한명씩만 친구 관계로 연결되어있는 것을 확인하면 된다. 

즉, DFS의 깊이가 4인지 확인하는 문제다. 

 

 

 

 

A - B(depth == 1)  - C(depth == 2)  - D(depth == 3)  - E(depth == 4)

  

 

 

if finish : return 을 통해 시간을 줄여준다. 

이미 finish가 True라면 깊이가 4인 dfs를 돌았다는 것이고 추가로 확인하지않아도 되기 때문이다. 

 

 

 

코드 : 

def dfs(now, depth) :
    global finish
    
    if finish : return 
    #  왔음을 표시 
    vis[now] = 1 
    if depth == 4 : 
        finish = 1 
        return 
    # 친구 목록을 돌면서 
    for i in f[now] : 
        if not vis[i] :
            dfs(i,depth+1)
            vis[i] = 0
    
    
if __name__=="__main__" :
    n,m = map(int,input().split())
    f = [[] for _ in range(n)]
    finish = 0 
    vis = [0]*(n+1)
    
    for i in range(m) :
        a,b = map(int,input().split())
        f[a].append(b)
        f[b].append(a)
        
    for i in range(n) :
        dfs(i,0)
        vis[i] = 0 
        if finish : break
    if finish : print(1)
    else : print(0)

 

 

 

 

참고 블로그 : 

https://jshong1125.tistory.com/19

[백준/Python(파이썬)] 13023 ABCDE