[파이썬] 백준 13023 : ABCDE (골드5)

[파이썬] 백준 13023 : ABCDE (골드5)

13023번: ABCDE

---

문제

---

풀이

0. 방향성 생각

• 재귀 깊이가 4번 추가되면 길이가 5인 친구관
• 계가 나온다.
• 재귀 깊이가 만족되면 탈출하고 print

1. 입력

import sys
iput = lambda : sys.stdin.readline().rstrip()

n,k = map(int,input().split())
graph = [[] for _ in range(n)]
for _ in range(k):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

 

2. 함수 정의

def dfs(x,depth):
    
    if depth == 5:
        return 1
    
    visit[x] = 1
    for nx in graph[x]:
        if not visit[nx]:
            if dfs(nx,depth+1):
                return 1
    visit[x] = 0
    return 0

for node in range(n):
    visit = [0]*n
    if dfs(node,1):
        print(1)
        break
else:
    print(0)

• visit을 dfs 내부에서 로컬변수로 쓰면 재귀 들어갈 때 마다 visit이 초기화된다.
• 따라서 노드에 방문처리를 하고 탐색을 한 후 탐색 끝나면 방문처리 다시 제거한다.
• 루트노드로 설정하고 탐색이 종료되면 다시 모든 visit을 0으로 만든다는 의미.
• 깊이가 5인 관계를 찾지 못하면 (재탐색이 필요한 경우) visit이 0으로 초기화 되어있어야함.

 

---

전체코드

import sys
iput = lambda : sys.stdin.readline().rstrip()

n,k = map(int,input().split())
graph = [[] for _ in range(n)]
for _ in range(k):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(x,depth):
    
    if depth == 5:
        return 1
    
    visit[x] = 1
    for nx in graph[x]:
        if not visit[nx]:
            if dfs(nx,depth+1):
                return 1
    visit[x] = 0
    return 0

for node in range(n):
    visit = [0]*n
    if dfs(node,1):
        print(1)
        break
else:
    print(0)