[BOJ] 13023번 - ABCDE

이 문제를 첫 시도 때 풀었다가 몇 일동안 고민에 빠졌다.. 내가 아는 dfs가 정확히 뭔지 고민을 많이 했던 문제였다.

bfs 와 dfs가 비슷한 개념으로 알고 있었고, 그에 따라서 어떤 노드들을 한 번만 탐색하는 것이라 생각했는데 

백트래킹을 dfs로 구현한다. 해서 헷갈렸던 것 같다. 아직까지 완벽하게 이해는 못했지만 어느 정도 개념이 잡히는 것 같다.

 

내가 아는 bfs, dfs는 노드들의 정점을 한 번만 순회하는 그래프에서의 그런 알고리즘이라 생각했다.

예를 들어 모든 노드들을 한 번 씩 탐색하는 것이다.

여기서 내가 알고싶었던 사실이 이런식으로의 dfs로 풀어버리면 1->3->2->4->5 이런 순으로 탐색은 못하지 않는가? 라는 것이다.

계속되는 고민끝에 하나 생각한 것은 일단 백트래킹은 완전탐색이며, 유망한지 검증하여 가지치기를 한다 라는 것이다.

 

예를 들어 백트래킹은 위 그래프를 토대로 이런 식으로 가지치며 완전탐색을 한다.

초기 1번 노드

1번 정점을 탐색한 뒤 다음 유망한 노드를 탐색

[1,2] , [1,3] 정점을 각각 순회했다.

유망 여부를 통해 끝까지 탐색한다.

 

백트래킹으로 (dfs)를 활용한 가지치기

 

이런 식으로 모든 경로들을 보는 것이다. 가지치기를 하며 깊이 있게 탐색하는 것을 백트래킹이라고 생각하면 될 것 같다.

탐색을 하면서 부모로 다시 돌아와 그 부분부터 다시 탐색하는 재귀적인 형태로 코드를 나타낼 수 있다.

 

www.acmicpc.net/problem/13023

13023번: ABCDE

 

1. 주어진 그래프를 백트래킹을 통해서 탐색한다.

2. 모든 정점을 root로 하는 백트래킹 중 조건에 일치하면 (즉, 친구 사이 관계가 4번 이상 이어질 때 탈출하고 뒤의 정점을 보지 않는다.)

 

from sys import stdin

std = stdin.readline

N, M = map(int, std().split())

friend = [[] for i in range(N)]

for i in range(M):
    a, b = map(int, std().split())
    friend[a].append(b)
    friend[b].append(a)

answer = []
ans = False

check = [0 for i in range(N)]


def dfs(b):
    global ans
    if len(answer) == 5:
        ans = True
        return

    for fr in friend[b]:
        if check[fr] == 0 and ans == False:
            check[fr] = 1
            answer.append(fr)
            dfs(fr)
            check[fr] = 0
            answer.pop()


for i in range(N):
    if ans == True:
        break
    answer = [i]
    check = [0 for i in range(N)]
    check[i] = 1
    dfs(i)

print("1" if ans else "0")