6. 탐색
6. 탐색
6.1 깊이 우선 탐색
깊이 우선 탐색의 핵심 이론
- 깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나이다.
- 깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘
| 기능 | 특징 | 시간 복잡도(노드 수: V, 에지 수: E) | | — | — | — | | 그래프 완전 탐색 | 재귀 함수로 구현
스택 자료구조 이용 | O(V+E) |
- 깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로에 유의해야 한다.
- 깊으 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다.
- DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하다.
- 그래프는 인접 리스트로 표현하고, DFS의 탐색 방식은 LIFO 특성을 가지므로 스택을 이용하겠다. (실제로는 주로 재귀함수로 많이 구현한다.)
1. DFS를 시작한 노드를 정한 후 사용할 자료구조 초기화하기
- DFS를 위해 필요한 초기 작업은 인접 리스트로 그래프 표현하기, 방문 배열 초기화하기, 시작 노드에 스택 삽입하기이다.
스택에 시작 노드를 1로 삽입할 때 해당 위치의 방문 배열을 체크하면 T, F, F, F, F, F가 된다.
2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기
- pop을 수행하여 노드를 꺼낸다.
꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하며 방문 배열을 체크한다. 방문 배열은 T, T, T, F, F, F가 된다.
3. 스택 자료구조에 값이 없을 때까지 반복하기
- 앞선 과정을 스택 자료구조에 값이 없을 때까지 반복한다.
이때 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심이다.
- 스택에서 3을 꺼내며 탐색 순서에 기록하고 인접 노드 4를 스택에 삽입하며 방문 배열에 체크한다. 4를 꺼내며 탐색 순서에 기록하고 6을 삽입하며 방문 배열에 체크한다. 6을 꺼내며 탐색 순서에 기록하고 6과 인접한 노드는 없으므로 추가 삽입은 없다.
- 계속해서 스택에서 2를 꺼내며 탐색 순서에 기록하고 2와 인접한 5, 6을 삽입하기 위해 본다.
- 이때 6은 방문 배열에 T로 체크되어 있으므로 5만 삽입한다.
- 이 과정을 스택에 빌 때까지 진행한다.
문제 023 : 연결 요소의 개수 구하기
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer>[] A;
static boolean visited[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokeninzer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
A = new ArrayList[n + 1];
visited = new boolean[n + 1];
for (int i=1; i<n+1; i++) { // 인접 리스트 초기화하기
A[i] = new ArrayList<Integer>();
}
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
A[u].add(v); // 양 방향 엣지이므로 양쪽에 엣지를 더하기
A[v].add(u);
}
int count = 0;
for (int i=1; i<n+1; i++) {
if (!visited[i]) { // 방문하지 않은 노드가 없을 때까지 방문하기
count++;
DFS(i);
}
}
System.out.println(count);
}
static void DFS(int v) {
if (visited[v]) {
return;
}
visited[v] = true;
for (int i : A[v]) {
if (visited[i] == false) { // 연결 노드 중 방문하지 않았던 노드만 탐색하기
DFS(i);
}
}
}
}
- 그래프를 인접 리스트로 저장하고 방문 배열도 초기화 한다. 방향이 없는 그래프이기 때문에 양쪽 방향으로 엣지를 모두 저장한다.
1
- 임의의 시작점에서 DFS를 수행한다. 현재의 경우 1을 시작점으로 정했다. 탐색을 마친 이후 방문한 곳은 1, 2, 5다.
1
- 아직 방문하지 않은 노드가 있으므로 시작점을 다시 정해 탐색을 진행한다. 현재의 경우 3, 4, 6 순서로 탐색을 마쳤다. 모든 노드를 방문했으니 전체 탐색을 종료한다.
1
- 1 ~ 3 과정을 통해 총 2번의 DFS가 진행되었다는 것을 알 수 있따. 즉, 연결 요소 개수는 2개다.
문제 024 : 신기한 소수 찾기
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
DFS(2, 1);
DFS(3, 1);
DFS(5, 1);
DFS(7, 1);
}
static void DFS(int number, int jarisu) {
if (jarisu == N) {
if (isPrime(number)) {
System.out.println(number);
}
return;
}
for(int i=1; i<10; i++) {
if (i%2 == 0) continue;
if (isPrime(number * 10 + i)) { // 소수라면 재귀함수로 자릿수를 늘림
DFS(number * 10 + i, jarisu +1);
}
}
}
static boolean isPrime(int num) {
for(int i=2; i<=num/2; i++) {
if (num % i == 0) return false;
}
return true;
}
}
발상
- 소수는 약수가 1과 자기 자신뿐인 수이다.
- 자릿수가 한 개인 소수: 2, 3, 5, 7
- 자릿수가 2개이상인 소수: 현재 수 * 10 + a를 계산하여 판단
- 소수라면 재귀 함수로 자릿수를 하나 늘린다.
- 단, a가 짝수인 경우는 제외.
- 이런 방식으로 자릿수를 N까지 확장 했을 때 그 값이 소수라면 해당 값을 출력한다.
1
문제 025 : 친구 관계 파악하기
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.util.*;
import java.io.*;
public class Main {
static ArrayList<Integer>[] friend;
static boolean[] visited;
static boolean found = false;
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());
friend = new ArrayList[N];
visited = new boolean[N];
for(int i=0; i<N; i++) {
friend[i] = new ArrayList<Integer>();
}
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
friend[a].add(b);
friend[b].add(a);
}
for(int i=0; i<N; i++) {
DFS(i, 1);
if(found) break;
}
System.out.println(found ? 1 : 0);
}
static void DFS(int v, int depth) {
if (found) return;
if (depth == 5 || found) {
found = true;
return;
}
visited[v] = true;
for(int i : friend[v]) {
if (visited[i] == false) { // 연결 노드 중 방문하지 않았던 노드만 탐색하기
DFS(i, depth + 1);
}
}
visited[v] = false;
}
}
- 모든 그래프가 연결이 되었느냐를 묻는 문제가 아니라, 특정 조건의 경로/관계를 묻는 문제
6.2 백트래킹
- 백트래킹은 문제를 해결하는 탐색 기법
- 문제를 해결할 수 있는 모든 경로를 탐색하면서 선택한 경로가 유효하지 않거나 조건에 만족하는 해를 찾지 못할 경우, 이전 단계로 되돌아가 다른 경로를 시도하는 알고리즘
| 기능 | 특징 | 시간복잡도(N: 분기 수, d: 탐색 깊이) | | — | — | — | | 문제를 해결할 수 있는 모든 경로 탐색 | 재귀 함수로 구현
가지치기로 성능 향상 | O(N^d) |
- 백트래킹은 일반적으로 재귀함수 형태로 구현, DFS와 구현 방식 매우 유사
- 가장 큰 특징은 가지치기로 유효하지 않은 경로를 초기에 배제하여 탐색 범위를 줄이고 성능을 높일 수 있다는 점
- DFS와의 차이점은, DFS가 모든 노드를 탐색하는 것을 목적으로 하는 반면, 백트래킹은 조건을 만족하는 해를 찾기 위해 불필요한 경로는 초기에 차단하며 효율적으로 탐색한다는 점
- 백트래킹을 활용할 수 있는 대표적인 문제로는 조합, 순열, N-Queens 문제 등이 있다.
백트래킹 핵심 이론
- 백트래킹은 문제를 해결하기 위해 가능한 경로를 탐색하면서, 조건을 만족하지 않는 경로를 가지치기하여 탐색 범위를 줄이는 것이 핵심이다.
- 이 과정은 기본적으로 재귀 함수를 이용해 구현하며, 다음 3단계로 작동한다.
- 가능한 선택지 탐색하기
- 현재 상태에서 가능한 선택지를 모두 탐색
- 유효성 검사 및 가지치기
- 각 선택지가 문제의 조건을 만족하는지 검사
- 만약 조건을 만족하지 않으면, 해당 경로는 더 이상 탐색하지 않고 즉시 이전 단계로 되돌아간다.
- 해답 도출하기
- 조건을 만족하는 해답을 찾으면 이를 기록하고, 필요에 따라 다른 경로도 계속 탐색한다.
- 가능한 선택지 탐색하기
문제 026 : N과 M
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static boolean[] V; // 숫자 사용 여부 저장하기
static int[] S; // 수열 정보 저장하기
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
S = new int[N];
V = new boolean[N];
backtracking(0);
}
private static void backtracking(int length) {
if(length == M) {
printArray();
return;
}
for(int i=0; i<N; i++) {
if (!V[i]) {
V[i] = true;
S[length] = i;
backtracking(length + 1);
V[i] = false;
}
}
}
private static void printArray() {
for(int i=0; i<M; i++) {
System.out.print(S[i] + 1 + " ");
}
System.out.println();
}
}
문제 027 : N-Queen 배치하기
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.io.*;
import java.util.*;
public class Main {
static int[] A; // 퀸 배치 정보 저장하기
static int N; // 체스판 크기 N*N
static int cnt = 0; // 퀸을 배치하는 경우의 수 저장하기
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
A = new int[N];
backtracking(0);
System.out.println(cnt);
}
private static void backtracking(int row) {
if (row == N) {
cnt++;
return;
}
for (int i=0; i<N; i++) {
A[row] = i;
if (check(row)) { // 배치한 퀸이 이전 퀸들과 서로 공격할 수 없는지 체크하기
backtracking(row + 1);
}
}
}
private static boolean check(int row) {
for(int i=0; i<row; i++) {
if (A[i] == A[row]) return false; // 일직선 배치
if (Math.abs(row - i) == Math.abs(A[i] - A[row])) return false; // 대각선 배치
}
return ture;
}
}
- 퀸을 공격할 수 없게 놓으려면 어떻게 놔야하는 지를 모름
- 체스에서 퀸은 가로, 세로, 대각선으로 공격할 수 있다.
- 같은 행에는 퀸이 1개만 존재할 수 있다.
- 즉, 모든 행에 퀸을 1개씩 배치해야 N개의 퀸을 서로 공격하지 않도록 놓을 수 있다.
- 따라서 맨 위 행부터 시작해 각 행마다 퀸을 하나씩 배치하며 가능한 모든 경우의 수를 찾는 방식으로 접근해야 함 → 백트래킹 알고리즘 이용
발상
- 가능한 선택지 탐색: 현재 행에서 퀸을 놓을 수 있는 위치를 탐색한다.
- 유효성 검사 및 가지치기: 해당 위치에 퀸을 배치할 때 다른 퀸과 서로 공격할 수 있는지 확인한다. 공격할 수 있다면 탐색을 종료하고 이전 단계로 돌아간다.
- 해답 도출: 마지막 행까지 퀸 배치를 모두 완료하면 경우의 수를 1 증가시키고, 백트래킹 전체를 종료하면 경우의 수를 출력한다.
1
- 이렇게 백트래킹 알고리즘을 수행하면서 마지막 행까지 퀸 배치를 완료하면 유효한 경우로 판단하여 경우의 수를 1 증가시킨다.
- 알고리즘을 모두 수행 완료한 후 경우의 수를 출력한다.
- 추가로 N x N인 체스판이 주어지므로 문제를 이차원 배열로 생각할 수 있지만, 의외로 다음과 같이 일차원 배열로도 퀸 배치 정보를 충분히 저장할 수 있다.
- 바로 일차원 배열의 인덱스를 행, 값을 열이라고 생각하는 방법이다.
1
- 퀸의 배치 정보를 일차원 배열로 저장하면 공격 가능 여부를 다음과 같이 쉽게 구현할 수 있다.
문제 028 : 색종이 붙이기
문제 분석
- 종이의 크기와 색종이의 개수가 크지 않으므로, 색종이를 붙일 수 있는 경우의 수를 모두 탐색해 보면 된다.
- 모든 경우의 수는 백트래킹 알고리즘을 이용하여 구한다.
1. 가능한 선택지 탐색 : 탐색은 색종이를 붙일 수 있는 1번째 위치를 찾는 것으로 시작한다. 탐색 위치는 왼쪽 위에서 시작하여 오른쪽으로 이동하고, 오른쪽 끝에 도달하면 한줄 아래로 내려가서 다시 왼쪽부터 이동하는 방식으로 진행한다.
2. 유효성 검사 및 가지치기 : 현재 선택한 위치에 가지고 있는 색종이를 붙일 수 있는지 확인한다. 사용할 수 있는 색종이의 크기는 다섯 종류이며, 크기별로 각각 최대 5장만 사용할 수 있다. 색종이를 해당 위치에 붙일 수 있다면 탐색을 계속 진행하고, 붙일 수 없다면 해당 탐색을 종료한다. 또한 목표는 사용한 색종이 개수를 최소화하는 것이므로, 현재까지 사용한 색종이 수가 이미 구한 최소값을 초과하면 탐색을 종료한다.
3. 해답 도출 : 모든 1을 덮는 탐색을 완료하면, 그 과정에서 사용한 색종이 수를 기록한다. 탐색을 모두 끝낸 뒤에는 이렇게 기록된 색종이 수 중에서 가장 작은 값을 찾아 출력한다.
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.io.*;
import java.util.*;
public class Main {
static int[][] M = new int[10][10];
static int[] S = {0, 5, 5, 5, 5, 5}; // 남은 색종이 수
static int result = Integer.MAX_VALUE; // 최소로 사용한 개수
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for (int i=0; i<10; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j=0; j<10; j++) {
M[i][j] = Integer.parseInt(st.nextToken());
}
}
// 1이 적힌 모든 칸을 붙일 때 사용한 색종이 개수에 대한 경우의 수를 백트래킹으로 탐색
backtracking(0, 0);
if (result == Integer.MAX_VALUE) {
System.out.println(-1);
} else {
System.out.println(result);
}
}
static void backtracking(int xy, int useCnt) {
// 색종이로 1이 적힌 모든 칸을 붙였을때 탐색 종료 (끝까지 탐색)
if (xy == 100) {
result = Math.min(useCnt, result);
return;
}
int x = xy % 10;
int y = xy / 10;
// 가지치기: 이전에 최소로 사용한 색종이 수보다 현재 탐색에서 사용한 색종이 수가 많으면 탐색 중단
if (result <= useCnt) return;
if (M[y][x] == 1) {
for (int i=5; i>0; i--) {
if (S[i] > 0 && check(x, y, i)) {
S[i]--; // 종이 사용하기
fill(x, y, i, 0); // 종이 붙이기: 종이로 덮이는 부분 1->0으로 변경
backtracking(xy + 1, useCnt + 1);
S[i]++; // 사용한 종이 다시 채우기
fill(x, y, i, 1) // 종이 떼어내기: 기존에 덮인 부분 0->1로 변경
}
}
} else {
backtracking(xy+1, useCnt); // 현재 좌표의 값이 0이면 바로 다음 칸으로 이동
}
}
static void fill(int x, int y, int size, int num) {
for (int i=y; i<y+size; i++) {
for (int j=x; j<x+size; j++) {
M[i][j] = num;
}
}
}
static boolean check(int x, int y, int size) {
if (x+size > 10 || y+size > 10) return false;
for (int i=y; i<y+size; i++) {
for (int j=x; j<x+size; j++) {
if (M[i][j] != 1) return false;
}
}
return true;
}
}
- 색종이로 1을 덮으면 해당 영역의 데이터를 0으로 변경 → 중복 방지
6.3 너비 우선 탐색
- 너비 우선 탐색도 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘
| 기능 | 특징 | 시간 복잡도 | | — | — | — | | 그래프 완전 탐색 | FIFO 탐색
Queue 자료구조 이용 | O(V + E) |
- 너비 우선 탐색은 선입선출 방식으로 탐색하므로 큐를 이용해 구현한다.
- 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.
너비 우선 탐색의 핵심 이론
1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
- BFS도 DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요하다.
그래프를 인접 리스트로 표현하는 것 역시 DFS와 동일. 차이점은 스택이 아닌 큐 이용
2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
- 큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입한다.
- 이때 방문 배열을 체크하여 이미 방문한 노드는 큐에 삽입하지 않는다.
큐에서 꺼낸 노드는 탐색 순서에 기록한다.
3. 큐 자료구조에 값이 없을 때까지 반복하기
- 큐에 노드가 없을 때까지 앞선 과정을 반복한다.
선입선출 방식으로 탐색하므로 탐색 순서가 DFS와 다름을 확인하세요.
문제 029 : DFS와 BFS 프로그램
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.io.*;
import java.util.*;
public class Main {
static boolean visited[];
static ArrayList<Integer>[] A;
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 start = Integer.parseInt(st.nextToken());
A = new ArrayList[N+1];
for(int i=1; i<=N; i++) {
A[i] = new ArrayList<Integer>();
}
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int S = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
A[S].add(E);
A[E].add(S);
}
// 번호가 작은 것부터 먼저 방문하기 위해 정렬하기
for(int i=1; i<=N; i++) {
Collections.sort(A[i]); // List 정렬
}
visited = new boolean[N+1]; // 방문 배열 초기화
DFS(start);
System.out.println();
visited = new boolean[N+1]; // 방문 배열 초기화
BFS(start);
System.out.println();
}
public static void DFS(int Node) {
System.out.print(Node + " ");
visitied[Node] = true;
for(int i : A[Node]) {
if (!visited[i]) {
DFS(i);
}
}
}
public static void BFS(int Node) {
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(Node);
visited[Node] = true;
while (!queue.isEmpty()) {
int now_Node = queue.poll();
System.out.print(now_Node + " ");
for (int i : A[now_Node]) {
if (!visited[i]) {
visited[i] = true;
queue.add(i);
}
}
}
}
}
문제 030 : 미로 탐색하기
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.io.*;
import java.util.*;
public class Main {
// 상하좌우를 탐색하기 위한 배열 선언하기
static int[] dx = { 0, 1, 0, -1 };
static int[] dy = { 1, 0, -1, 0 };
static boolean[][] visited;
static int[][] A;
static int N, M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenzier st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
A = new int[N][M];
visited = new boolean[N][M];
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
String line = st.nextToken();
for(int j=0; j<M; j++) {
A[i][j] = Integer.parseInt(line.substring(j, j+1));
}
}
BFS(0, 0);
System.out.println(A[N-1][M-1]);
}
public static void BFS(int i, int j) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {i, j});
visited[i][j] = true;
while (!queue.isEmpty()) {
int now[] = queue.poll();
for (int k=0; k<4; k++) {
int x = now[0] + dx[k];
int y = now[1] + dy[k];
if (x >= 0 && y >= 0 && x < N && y < M) {
if (A[x][y] != 0 && !visited[x][y]) { // 갈 수 있는 칸 && 방문 검사하기
visited[x][y] = true;
A[x][y] = A[now[0]][now[1]] + 1; // 깊이 업데이트 하기
queue.add(new int[] {x, y});
}
}
}
}
}
}
문제 031 : 트리의 지름 구하기
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.io.*;
import java.util.*;
public class Main {
static boolean[] visited;
static int[] distance;
static ArrayList<Edge>[] A;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
A = new int[N+1];
for(int i=1; i<=N; i++) {
A[i] = new ArrayList<Edge>();
}
for(int i=0; i<N; i++) {
StringTokenzier st = new StringTokenizer(br.readLine());
int S = Integer.parseInt(st.nextToken());
while(true) {
int E = Integer.parseInt(st.nextToken());
if (E == -1) break;
int V = Integer.parseInt(st.nextToken());
A[S].add(new Edge(E, V));
}
}
distance = new int[N+1];
visited = new boolean[N+1];
BFS(1);
int max = 1;
for(int i=2; i<=N; i++) {
if (distance[max] < distance[i]) max = i;
}
distance = new int[N+1];
visited = new boolean[N+1];
BFS(max);
Arrays.sort(distance);
System.out.println(distance[N]);
}
public static void BFS(int index) { // BFS 구현하기
Queue<Integer> queue = new LinkedList<>();
queue.offer(index);
visited[index] = true;
while (!queue.isEmpty()) {
int now_node = queue.poll();
for (Edge i : A[now_node]) {
int e = i.e;
int v = i.value;
if (!visited[e]) {
visited[e] = true;
queue.add(e);
distance[e] = distance[now_node] + v; // 거리 배열 업데이트하기
}
}
}
}
}
class Edge {
int e;
int value;
public Edge(int e, int value) {
this.e = e;
this.value = value;
}
}
가장 긴 경로 찾기 아이디어
- 임의의 노드에서 가장 긴 경로로 연결돼 있는 노드는 트리의 지름에 해당하는 두 노드 중 하나다.
6.4 이진 탐색
- 이진 탐색은 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘
- 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.
| 기능 | 특징 | 시간 복잡도 |
|---|---|---|
| 타깃 데이터 탐색 | 중앙값 비교를 이용한 대상 축소 방식 | O(log N) |
이진 탐색의 핵심 이론
- 이진 탐색은 오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복한다.
- 내림차순이라면 조건을 반대로 하여 과정을 반복하면 된다.
이진 탐색 과정
- 현재 데이터셋의 중앙값을 선택한다.
중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.- 과정 1~3을 반복하다가
중앙값 == 타깃 데이터일 때 탐색을 종료한다.
다음은 총 16개의 데이터가 있는 데이터셋에서 값이 55인 데이터를 찾는 과정이다.
문제 032 : 원하는 정수 찾기
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] A = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
int M = Integer.parseInt(br.readLine());
int[] nums = new int[M];
st = new StringTokenizer(br.readLine());
for(int i=0; i<M; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(A);
StringBuilder sb = new StringBuilder();
for(int i=0; i<M; i++) {
int start = 0;
int end = N-1;
int pivot = (start + end) / 2;
while(start <= end) {
pivot = (start + end) / 2;
if (A[pivot] == nums[i]) {
sb.append(1+"\n");
break;
}
else if (A[pivot] > nums[i]) end = pivot-1;
else start = pivot+1;
}
if(A[pivot] != nums[i]) sb.append(0+"\n");
}
System.out.println(sb.toString());
}
}
- N의 최대 범위가 100,000이므로 단순 반복문으로는 이 문제를 풀 수 없다.
- 이진 탐색을 적용하면 O(nlogn) 시간 복잡도로 해결할 수 있으므로 이진 탐색을 적용해야 한다.
문제 033 : 블루레이 만들기
풀이
- 문제 분석
- 블루레이의 크기가 모두 같고 녹화 순서가 바뀌지 않아야 함이라는 문제 조건이 이진 탐색 알고리즘을 선택하게 하는 실마리.
- 블루레이에 첫 레슨부터 마지막 레슨까지 차례대로 저장하다보면 지정한 블루레이 크기로 모든 레슨을 저장할 수 있는지 판단할 수 있기 때문이다.
- 풀어 보기
- 이진 탐색의 시작 인덱스는 최대 길이의 레슨 (ex. 9)
- 종료 인덱스는 모든 레슨 길이의 합 (ex. 45)
- 블루레이 개수가 3일 때 9~45 사이에서 블루레이 크기의 최솟값을 이진 탐색으로 찾으면 된다.
- 우리는 ‘블루레이 크기를 얼마로 해야하는 지’를 결정해야 한다.
- 문제의 정답은.. “숫자 하나”이다.
- 그렇다면 이 순간 “정답의 범위를 탐색하는 문제인가?”를 생각한다.
- 블루레이 크기는 어디부터 어디까지 가능할까?
- 강의 중 가장 긴 게 9라고 할 때, 8은 절대 불가능이다. 왜냐하면 9를 담지 못하기 때문
- 즉, 블루레이 크기는 최소한 가장 긴 강의 이상이어야 한다.
- 최대값을 생각할 땐, “블루레이 크기를 얼마나 크게 잡으면 무조건 가능할까?”를 생각하면 된다.
- 가장 극단적인 상황은 모든 강의를 블루레이 1개에 넣는 것이고, 그건 모든 강의 길이의 합이다.
- 9 ~ 45 사이에서 이진 탐색을 다음과 같이 수행한다. 이진 탐색은
시작 인덱스 > 종료 인덱스일 때까지 수행한다.
- 이진 탐색 수행
- 중앙값 크기로 모든 레슨을 저장할 수 있으면
종료 인덱스 = 중앙값 - 1 - 중앙값 크기로 모든 레슨을 저장할 수 없으면
시작 인덱스 = 중앙값 + 1
- 중앙값 크기로 모든 레슨을 저장할 수 있으면
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.*;
import java.io.*;
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[] len = new int[N];
st = new StringTokenizer(br.readLine());
int start = 0;
int end = 0;
for(int i=0; i<N; i++) {
len[i] = Integer.parseInt(st.nextToken());
if (start < len[i]) start = len[i];
end += len[i];
}
while(start <= end) {
int pivot = (start + end) / 2;
int sum = 0;
int count = 0;
for (int i=0; i<N; i++) {
if (sum+len[i] > pivot) {
count++;
sum = 0;
}
sum = sum + len[i];
}
if (sum != 0) count++;
if (count > M) start = pivot +1;
else end = pivot -1;
}
System.out.println(start);
}
}
문제 034 : 배열에서 K번째 수 찾기 (이해못함)
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int K = Integer.parseInt(br.readLine());
long start = 1, end = K;
long ans = 0;
// 이진 탐색 수행하기
while (start <= end) {
long middle = (start + end) / 2;
long cnt = 0;
// 중앙값보다 작은 수는 몇 개인지 계산하기
for (int i=1; i<=N; i++) {
cnt += Math.min(middle / i, N); // 작은 수를 카운트하는 핵심 로직
}
if (cnt < K) {
start = middle + 1;
} else {
ans = middle; // 현재 단계의 중앙값을 정답 변수에 저장하기
end = middle - 1;
}
}
System.out.println(ans);
}
}
- 이진 탐색으로 중앙값보다 작은 수의 개수를 세면서 범위를 절반씩 줄이는 방법으로 B[k]를 구한다.
- 다시 말해 작은 수의 개수가 k-1개인 중앙값이 정답이다.
- 핵심: 정렬된 배열을 직접 만들지 않고, 어떤 숫자 X가 몇 번째인지 계산해서 찾는다.
- 곱셈표의 i번째 행은 i의 배수들로 이루어져 있으므로,
mid보다 작거나 같은 수의 개수는mid / i로 계산할 수 있다. 단, 한 행에는 최대 N개까지만 존재하므로min(mid / i, N)을 사용하고, 이를 모든 행에 대해 더하면 mid 이하의 숫자가 전체에서 몇 개인지 알 수 있다. - 이 개수가 k보다 작다면 아직 k번째 수에 도달하지 못한 것이므로 더 큰 값을 찾아야 하고, k 이상이라면 mid가 k번째 수가 될 가능성이 있으므로 더 작은 값에서도 가능한지 확인한다. 이렇게 값의 범위를 이진 탐색으로 줄여가면, 결국 정렬했을 때 정확히 k번째에 오는 최소 값을 찾게 된다.
- 곱셈표의 i번째 행은 i의 배수들로 이루어져 있으므로,
This post is licensed under CC BY 4.0 by the author.