BOJ 백준 파이썬 13023 ABCDE

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

문제의 조건이다.

이것을 그래프로 그려보자

길이가 4or5(설정하기 나름) 그래프를 탐색할 수 있는가?를 물어보고 있다.

DFS탐색으로 탐색하면 된다.

여기서 주의할 점은 이미 방문한 곳은 dfs함수에서 반환될 때 visit에서 방문해제를 시켜야한다는 점

 

 

import sys
from collections import deque
from itertools import combinations
 
 
 
def dfs(x,length):
    if length==5:
        print(1)
        exit()
    else:
        for y in graph[x]:
            if check[y]==-1:
                check[y]=1
               # print(length)
                dfs(y,length+1)
                check[y]=-1
 
if __name__=='__main__':
    #sys.stdin=open("input.txt", "rt")
    
    n,m=map(int,input().split()) ##n=사람 수, m=친구 관계 수
   
    graph=[[] for _ in range(n)] 
 
    
    for _ in range(m):
        a,b=map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
 
    for i in range(0,n):
        check=[-1]*(n)
        check[i]=1
        dfs(i,1)
 
    print(0)