BFS, DFS, Backtracking

BFS, DFS, Backtracking

나무위키

너비우선탐색 (Breadth First Search, BFS)

루트 노드의 자식노드들을 먼저 모두 차례로 방문, 이렇게 방문했던 자식 노드들의 그 자식들을 차례로 방문하는 방식.

즉, 루트 -> 자식1 -> 자식2 -> 자식3 -> 손자(?)1 -> 손자2.. 이런식

Queue 사용 : 인접한 노드들을 탐색 후, 차례로 다시 너비(높이(레벨)가 같은) 우선 탐색을 해야함.. 따라서 선입선출을 이용해야한다

이때 index를 이용해 탐색한다. 즉, Integer타입 (왼쪽자식은 x2, 오른쪽자식은 x2+1)

Queue q = new LinkedList<>();

깊이우선탐색 (Depth First Search, DFS)

루트 노드에서 출발해 깊이 탐색하다가 더 이상 갈 수 없으면, 가장 마지막에 만났던 노드로 돌아가 다른 방향의 노드로 탐색을 반복하여 모든 노드를 방문하는 방식

Stack 또는 재귀 사용 : 마지막에 만났던 갈림길의 노드로 되돌아가서 다시 깊이우선탐색을 반복하기 때문에 ,,

Backtracking

DFS를 수행한다. 각 노드의 유망성을 확인. 유망하지 않으면 가지치기(prunig) --> 유망하지 않으면 그 노드의 부모로 돌아가서 다른 노드의 검색을 계속한다.(불필요한 경로 미리 차단)

주의 : 1%의 가능성이 있으면 탐색해야한다.

또한, 최악의 경우 지수함수(선택지^depth) 형태로 시간복잡도가 나타나기 때문에 처리 불가할 수 있다.

Backtracking 예시

Q. 체스를 둘 때 서로 위협하지 않게 8개의 Queen을 배치하려면 몇가지 경우가 있는지?

위협 조건 : 같은 행, 같은 열, 양쪽 대각선

package com.ssafy.w0819; import java.util.Scanner; //backtracking : 유망성과 가지치기 //유망하지 않으면 부모로 돌아가 다음 자식 노드로 간다 //같은 행에 두지 않는 방식 // N개의 퀸을 위협적이지 않게 놓는 모든 경우의 수 public class NQueenTest_backtracking { static int N, cnt; static int col[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); // 퀸을 놓을 때 상태를 나타낼 때의 배열? // -> 같은 행에 두지 않는 전제 조건으로 1차원 배열..로 열을 나타내기 col = new int[N + 1]; // 1부터 쓰기 위해 0 index 사용안하겠음 cnt = 0; setQueens(1); // 1행부터 놓는 시도 System.out.println(cnt); } // 퀸을 놓는 메소드 private static void setQueens(int rowNo) { // 행번호를 파라미터로 받기 //유망성 체크 : rowNo - 1 까지 (직전까지 놓았던 퀸을) 체크해야한다. if(!isAvailable(rowNo-1)) return; // 가능하지 않으면 리턴으로 종료 // 만약 Q3까지 유망성을 체크했다면 이전인 Q2 와만 비교하면된다. 이미 유망성 체크한 것을 다시 체크할 필요X //기저 조건 if(rowNo>N) { //N행(마지막행)까지 놓고 종료 cnt++; return; } // 유도조건 // 현재 퀸 1열부터 N열까지 놓아보기 (상태를 기억) // 놓았으면 다음 퀸 놓으러 가기 for(int i = 1; i <= N; i++) { col[rowNo] = i; //각 행에 놓아진 열 위치를 저장.. 계속 덮어서 재사용?? //두가지 방법.. // 첫 번째 : 유망하지 않으면 backtracking setQueens(rowNo+1); } } //유망성 체크 private static boolean isAvailable(int rowNo) { // rowNo : 현재 검사하려는 퀸 // 1행퀸이면 2행 퀸까지 비교하면된다. for(int k = 1; k < rowNo; k++) { // k : 이전 퀸 //직전 퀸을 비교해야하므로 k <= rowNo가 아니다. if(col[rowNo] == col[k] || Math.abs(col[rowNo] - col[k]) == (rowNo - k) ) return false; // 같은열 : 현재 퀸열과 직전 퀸 열과 같으면 유망 X // 대각선 조건은?@@ 행차이와 열차이가 같다!!!!!!!!!!!!!!!! 개신기행.. } return true; //가능성있다!~ } }

from http://elevensix.tistory.com/43 by ccl(A) rewrite - 2021-08-19 22:26:21