[๋ฐฑ์ค€] 13023 ABCDE

DFS
avatar
2025.01.17
ยท
2 min read

2864

๐Ÿ”— ๋ฌธ์ œ ๋งํฌ

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)์ด๋‹ค.







- ์ปฌ๋ ‰์…˜ ์•„ํ‹ฐํด