ing..[알고리즘][6월 셋째 주][그래프] 백트래킹 (backtracking)
📌 주제 : 백트래킹 (backtracking)
그래프의 모든 노드를 탐색(=완전 탐색)하여 해를 찾는 대표적인 방법으로 DFS, BFS 가 있다. 이러한 완전 탐색 방법은 해가 될 가능성이 없는 조합까지도 모두 시도해보아 비효율적이라는 단점이 존재한다. 또한 일반적으로 재귀 함수를 이용해 구현하는데, 재귀 함수가 시간적으로 효율적인 방법이 아닌데다가 호출 횟수가 시간복잡도가 되기 때문에 호출 횟수를 줄여 시간적인 효율성을 높이는 것이 중요하다.
백트래킹 알고리즘은 어떤 노드의 유망성을 점검한 후에 유망하지 않다고 판단되면, 더이상 해당 노드의 경로를 탐색하지 않는 방법으로 효율성을 높일 수 있는 방법이다. "유망하냐, 안하냐"에 대한 판단은 문제에 따라 다를 것이다. 유망함에 대한 판단 자체가 가능한 지 먼저 고려해야하고, 가능하다고 한다면 유망함의 판단이 얼마나 정확한 지도 고려해야할 것이다.
그리고 시간적 효율성이 매우 중요한 경우, 유망함에 대한 판단이 100% 정확하지 않아 해를 찾아내는 데 실패할 위험성을 감수하더라도 백트래킹을 수행하는 경우도 있다. 살을 내주고 뼈를 취하는 전략이랄까? 단, 경험적인 근거를 활용해 최대한 실패가능성을 줄여야 하겠다.
- 유망함 promissing : 어떤 노드를 방문했을 때, 그 노드를 포함한 경로가 해답이 될 수 있으면 유망하다고 한다.
- 가지치기 pruning : 유망하지 않은 노드가 포함되는 경로는 탐색하지 않는다.
- 백트래킹 backtracking : 유망하지 않은 노드의 부모 노드로 돌아간다.
백트래킹의 과정
- 깊이 우선 탐색을 실시한다.
- 방문한 노드가 유망한지 점검한다.
- 유망하지 않으면, 해당 노드의 부모 노드로 돌아가 탐색을 계속한다.
- 유망하면 탐색을 계속한다.
백준 9663번 : N-Queen
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
문제 분석
N x N 체스판에서 N 개의 Queen 을 서로 공격할 수 없도록 배치하는 문제이다. Queen 은 아래 그림처럼 모든 직선방향으로 공격이 가능하다.
그림을 그려가며 규칙을 찾아보았다. (그려 가다보니 감을 잡았다.) 우선 첫 Queen 을 배치하고 더 이상 놓을 수 없는 칸에 X표시, 가능한 칸에 O표시를 한다. 만약 남은 Queen 의 개수보다 O표시된 칸이 많거나 같으면 유망한 것으로 볼 수 있고, 반대의 경우 가능성이 없으므로 유망하지 않다. 유망할 경우, 다시 Queen을 배치하고 앞서 과정을 반복한다.
구현 코드
서치 중에 발견한 팁이 있다. 2차원 배열을 1차원 배열로 표현할 수 있는 방법이다. 2차원 배열에서 '요소의 값' 자체는 의미가 없어 아무 값이나 가능할 때 사용가능하다. 1차원 배열로 각 요소의 index 를 '열'로 생각하고, 요소의 값을 '행'으로 생각한다. 이번 문제로 예를 들어보자. Queen을 배치할 수 있는 공간을 [2,0,3,1] 로 표현하면, [3행 1열], [1행 2열], [4행 3열], [2행 4열] 에 배치할 수 있다는 뜻이 된다.(배열은 0부터 시작)
[참고]
https://st-lab.tistory.com/118
https://velog.io/@khyunjiee/TIL-Backtracking-Graph
벨만포드 알고리즘
다익스트라 알고리즘
플로이드 워셜 알고리즘
-> 최단거리 알고리즘 종류들
간선의 단방향 양방향
ㄹ자바에 priority queue 가 잇음.
https://www.acmicpc.net/problem/1916
https://www.acmicpc.net/problem/24480
https://www.acmicpc.net/problem/1697
- 강한 결합 요소 문제도 봐라
책추천
오브젝트 : 코드로 배우는 객체지향 설계
클린코드