[python]13023_ABCDE

사용한 자료구조 및 개념 : DFS, 백트래킹

 

💡 문제풀이 아이디어 및 어려웠던 점

💫 아이디어

1️⃣ 5개의 노드가 연속적으로 이루어진 경우가 있으면 1을 출력하는 문제이다.

2️⃣ dfs 재귀를 활용하여 깊이가 4인 경우를 찾는다.

dfs에 현재 노드와 깊이를 인자로 넘겨준다!

3️⃣ 깊이가 4인 경우 result값을 1로 바꾸고 return하여 함수를 탈출! 반복문도 break한다!

4️⃣ 끝까지 탐색했는데도 깊이가 4가 되지 않는다면 재탐색을 해야하므로 현재 노드(v)를 False로 바꿔준다. ⇒ 백트래킹!

✅ 백트래킹이란?
Promising : 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크한다.
Pruning : 해당 트리에서 조건에 맞지않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고 가지치기를 한다. 

---

Solution Code & 주석

import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)

def dfs(v, d):
    global result
    visited[v] = True

    if d == 4:
        result = 1
        return

    for next_v in graph[v]:
        if not visited[next_v]:
            dfs(next_v, d + 1)
    visited[v] = False

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
visited = [False] * n
result = 0

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

for now in range(n):
    dfs(now, 0)
    if result == 1:
        break

print(result)