Development Palette
BFS, DFS, Backtracking 본문
너비우선탐색 (Breadth First Search, BFS)
- 루트 노드의 자식노드들을 먼저 모두 차례로 방문, 이렇게 방문했던 자식 노드들의 그 자식들을 차례로 방문하는 방식.
- 즉, 루트 -> 자식1 -> 자식2 -> 자식3 -> 손자(?)1 -> 손자2.. 이런식
- Queue 사용 : 인접한 노드들을 탐색 후, 차례로 다시 너비(높이(레벨)가 같은) 우선 탐색을 해야함.. 따라서 선입선출을 이용해야한다
- 이때 index를 이용해 탐색한다. 즉, Integer타입 (왼쪽자식은 x2, 오른쪽자식은 x2+1)
Queue <Integer> q = new LinkedList<>();깊이우선탐색 (Depth First Search, DFS)
- 루트 노드에서 출발해 깊이 탐색하다가 더 이상 갈 수 없으면, 가장 마지막에 만났던 노드로 돌아가 다른 방향의 노드로 탐색을 반복하여 모든 노드를 방문하는 방식
- Stack 또는 재귀 사용 : 마지막에 만났던 갈림길의 노드로 되돌아가서 다시 깊이우선탐색을 반복하기 때문에 ,,
무방향 그래프 인접리스트로 구현
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
package com.hotfive.workbook.b1260_DFS와BFS;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
//https://www.acmicpc.net/problem/1260
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); //정점개수
int M = Integer.parseInt(st.nextToken()); //간선갯수
int V = Integer.parseInt(st.nextToken()); //탐색을 시작할 정점의 번호
//방문체크 배열
boolean [] visited = new boolean[N+1];
// 정점마다 연결해 줄 인접리스트 배열생성
LinkedList<Integer>[] adjlist = new LinkedList[N+1];
for (int n = 1; n <= N; n++) {
adjlist[n] = new LinkedList<>(); // 해당 정점에 연결된 정점들이 담겨있는 리스트
}
// 정점 연결 // 무방향 간선 연결
for (int m = 0; m < M; m++) {
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken()); // 연결할 정점 v1, v2
int v2 = Integer.parseInt(st.nextToken());
adjlist[v1].add(v2);
adjlist[v2].add(v1);
}
// 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하기 위해 오름차순 정렬
for (int n = 1; n <=N; n++) {
Collections.sort(adjlist[n]);
}
// DFS, BFS 실행
dfs(V, adjlist, visited);
visited = new boolean[N+1];
System.out.println();
bfs(V, adjlist, visited);
br.close();
}
private static void dfs(int v, LinkedList<Integer>[] adjlist, boolean[] visited) {
visited[v] = true;
System.out.print(v + " ");
for (int n : adjlist[v]) {
if (visited[n]) continue;
dfs(n,adjlist,visited);
}
}
public static void bfs(int v, LinkedList<Integer>[] adjList, boolean[] visited) {
Queue<Integer> queue = new LinkedList<>();
queue.add(v);
visited[v]= true;
while (!queue.isEmpty()){
v = queue.poll();
System.out.print(v + " ");
for (int n : adjList[v]) {
if(visited[n]) continue;
visited[n] = true;
queue.add(n);
}
}
}
}
/*
4 5 1
1 2
1 3
1 4
2 4
3 4
*/
Backtracking
- DFS를 수행한다.
- 각 노드의 유망성을 확인.
- 유망하지 않으면 가지치기(prunig) --> 유망하지 않으면 그 노드의 부모로 돌아가서 다른 노드의 검색을 계속한다.(불필요한 경로 미리 차단)
- 주의 : 1%의 가능성이 있으면 탐색해야한다.
- 또한, 최악의 경우 지수함수(선택지^depth) 형태로 시간복잡도가 나타나기 때문에 처리 불가할 수 있다.
Backtracking 예시
Q1. 체스를 둘 때 서로 위협하지 않게 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; //가능성있다!~
}
}
package com.ssafy.w0819;
import java.util.Scanner;
// 두 번째 방법 : 유망성체크를하고 돌아가지 않아도 되는 방법
//같은 행에 두지 않는 방식
// N개의 퀸을 위협적이지 않게 놓는 모든 경우의 수
public class NQueenTest2_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; //각 행에 놓아진 열 위치를 저장.. 계속 덮어서 재사용??
//두번째 방법 : 유망성 체크를하고 바로 가는 방법~!!
if(isAvailable(rowNo)) {
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; //가능성있다!~
}
}
Q2. 부분집합의 합이 특정 숫자(자연수)를 만족시키려면 몇가지 경우의 수가 있는지?
--> 백트랙킹을 이용하면 매우 적은 호출 횟수로 탐색할 수 있다!
package com.ssafy.w0819;
import java.util.Scanner;
/**
*w0805 S2_SubSetSumTest 코드 변환
*/
//부분집합 합 문제_ 백트레킹
import java.util.Scanner;
public class SubSetSumTest {
static int N,totalCnt2,totalCnt3,S;
static int[] input;
static boolean[] isSelected;
static int callCnt2, callCnt3;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
S = sc.nextInt();
input = new int[N];
isSelected = new boolean[N];
callCnt3 = callCnt2 = totalCnt3 = totalCnt2 = 0;
for (int i = 0; i < N; i++) {
input[i] = sc.nextInt();
}
generateSubset2(0,0);
System.out.println("경우의 수 : "+totalCnt2+", 호출횟수 : "+callCnt2);
generateSubset3(0,0);
System.out.println("경우의 수 : "+totalCnt3+", 호출횟수 : "+callCnt3);
}
// 가지치기 하지 않은 버전
private static void generateSubset2(int cnt,int sum){ // cnt : 부분집합을 처리하기 위해 고려된 원소수
// sum : 기존까지 부분집합 구성원소들의 합
callCnt2++;
if(cnt == N) {
// 부분집합 완성
// 부분집합의 합 == 목표합 체크
if(sum == S) {
totalCnt2++;
for (int i = 0; i < N; i++) {
if(isSelected[i]) System.out.print(input[i]+" ");
}
System.out.println();
}
return;
}
// 현재 원소를 부분집합에 넣기
isSelected[cnt] = true;
generateSubset2(cnt+1, sum+input[cnt]);
// 현재 원소를 부분집합에 넣지 않기
isSelected[cnt] = false;
generateSubset2(cnt+1, sum);
}
private static void generateSubset3(int cnt,int sum){ // cnt : 부분집합을 처리하기 위해 고려된 원소수
// sum : 기존까지 부분집합 구성원소들의 합
callCnt3++;
// 부분집합의 합 == 목표합 체크
if(sum == S) {
totalCnt3++;
for (int i = 0; i < N; i++) {
if(isSelected[i]) System.out.print(input[i]+" ");
}
System.out.println();
return;
}
if(sum>S || cnt==N) return;
// 현재 원소를 부분집합에 넣기
isSelected[cnt] = true;
generateSubset3(cnt+1, sum+input[cnt]);
// 현재 원소를 부분집합에 넣지 않기
isSelected[cnt] = false;
generateSubset3(cnt+1, sum);
}
}input
5
21
5 21 11 16 6 10
output
5 16
21
경우의 수 : 2, 호출횟수 : 63
5 16
21
경우의 수 : 2, 호출횟수 : 29
'Algorithm > 개념' 카테고리의 다른 글
| 무방향 그래프 인접 리스트 - BFS, DFS (0) | 2021.08.24 |
|---|---|
| 분할정복기법 응용2 (0) | 2021.08.19 |
| [순열] 비트마스크로 순열 (0) | 2021.08.18 |
| [순열, 조합] NextPermutation (0) | 2021.08.18 |
| 이진 검색 (0) | 2021.08.18 |
Comments