문제 링크
문제 풀이
- 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)
반응형
'Coding Test > BOJ' 카테고리의 다른 글
[백준/Python] 2251 물통 (2) | 2024.03.14 |
---|---|
[백준/Python] 2225 합분해 (0) | 2024.03.12 |
[백준/Python] 1021 회전하는 큐 (0) | 2024.02.25 |
[백준/Python] 16564 히오스 프로게이머 (0) | 2024.02.24 |
[백준/Python] 2589 보물섬 (0) | 2024.02.23 |