
๐ ๋ฌธ์ ๋งํฌ
https://www.acmicpc.net/problem/13023
๐ป ์ฝ๋
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n,m = map(int,input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
a,b = map(int,input().split())
graph[a].append(b)
graph[b].append(a)
result = 0
visited = [0] * n
def dfs(start,cnt):
global result
if cnt == 5:
result = 1
return
visited[start] = 1
for node in graph[start]:
if not visited[node]:
dfs(node,cnt+1)
visited[start] = 0
return
for i in range(n):
dfs(i,1)
if result:
break
print(result)
๐คทโโ ํ์ด
์น๊ตฌ๊ด๊ณ ๊ทธ๋ํ์์ ์ฐ์๋ 5๋ช ์ ์น๊ตฌ๊ด๊ณ๊ฐ ์กด์ฌํ๋์ง ํ์ธํ๋ ๋ฌธ์ ์ด๋ค.
์ธ์ ๋ฆฌ์คํธ ๋ฐฉ์์ผ๋ก ์น๊ตฌ ๊ด๊ณ๋ฅผ ์ถ๊ฐํ๋ค.
cnt == 5
(์ฐ๊ฒฐ๋ 5๋ช )์ด๋ฉด result = 1 ํ ์ข ๋ฃํ์ ํ
visited[start] = 0
์ผ๋ก ๋ฐฉ๋ฌธ ํด์ โ ๋ค๋ฅธ ๊ฒฝ๋ก ํ์ ๊ฐ๋ฅ๋ชจ๋ ๋ ธ๋์์ ํ์์ ์์ํ๋ค.
์ต์ ์ ๊ฒฝ์ฐ ๋ชจ๋ ๋ ธ๋์์ DFS๋ฅผ ์์ํ๋ฏ๋ก O(n^2)์ด๋ค.