[백준/Python] 13023 ABCDE

문제 링크

13023번: ABCDE

 

문제 풀이

• 5명이 한 번에 연결되어 있다면 1을 출력, 아니면 0을 출력한다.
• 리스트 안의 값을 처음부터 반복문을 돌리면서 탐색한다.
• 만약 깊이 우선 탐색을 진행하다가 더 이상 진행할 수 없을 때는 다시 돌아와야 하므로, 기존 방문했던 값을 다시 False로 바꿔야 한다.

 

전체 코드

import sys
sys.setrecursionlimit(10 ** 7)

def dfs(s, v, c):
    global res
    v[s] = True
    if c == 5:
        res = 1
        return
    for i in arr[s]:
        if not v[i]:
            dfs(i, v, c+1)
    v[s] = False

n, m = map(int, sys.stdin.readline().split())
arr = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    arr[a].append(b)
    arr[b].append(a)

visited = [False] * n

res = 0
for i in range(n):
    dfs(i, visited, 1)

print(res)