목록백트래킹 (9)

Doby's Lab

[알고리즘] 백준 15650번: N과 M (2) (C++), Backtracking의 개념, DFS와의 차이

(N과 M (1) 문제를 중심으로 설명하려 했으나 Backtracking과 DFS의 차이를 설명하기 위해 N과 M (2) 문제가 적합하다는 생각이 들었다.) 개념 백트래킹은 DFS를 응용하여 나온 알고리즘 같았다. DFS에 대해서는 그래프 이론에 대한 문제를 풀기 시작할 때 제대로 다시 다루겠지만 간단히 정리하면 어떠한 그래프가 주어졌을 때, 시작 노드로부터 연결돼있는 모든 노드를 탐색해나가는 완전 탐색 알고리즘이다. 또한 노드끼리 연결되었는가도 따져보아야 하는데 다음에 다시 다루겠다. 이러한 그래프가 있다고 가정하자. 시작 노드가 1일 때, DFS는 모든 노드들을 다음과 같이 탐색해나간다. 백트래킹은 DFS에 어떠한 조건을 주어서 (조건이라고 해서 무조건 if문을 사용하지 않는다.) 원하는 부분만 탐색..
PS/BOJ 2021. 9. 16. 20:26
이전 Prev 1 2 Next 다음