[백준/파이썬] 13023번 ABCDE

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

13023번: ABCDE

dfs 연습하기 좋은 문제이다.

 

우선 양방향 그래프이므로 입력을 양쪽에 모두 넣어주어야 한다는 것을 잊지말자!

 

그리고 숫자 하나씩 dfs를 돌려보며, 재귀의 depth가 4 (=> A-B, B-C, C-D, D-E 의 친구 관계) 에 도달할 경우 True 값을 주고 반환하면 된다. 단 한번이라도 도달하면 1을 출력해주면 된다.

 

주의할 점은, dfs에 들어가기 전 해당 숫자에 대해 방문 체크를 해주고 시작해야한다!

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

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

friend = [[] for _ in range(n)]
visited=[False for _ in range(n)]

for _ in range(m):
  a ,b = map(int,input().split())
  friend[a].append(b)
  friend[b].append(a)
  
def dfs(now,depth):
  global ans
  if depth == 4:
    ans=True
    return
  
  for x in friend[now]:
    if not visited[x]:
      visited[x] = True
      dfs(x,depth + 1)
      visited[x] = False
    
for i in range(n):
    visited[i] = True
    dfs(i,0)
    visited[i] = False
    if ans:
        break

if ans: print(1)
else: print(0)