너비 우선 탐색(Breadth-first search, BFS)
① 너비 우선 탐색이란?
▷ 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘입니다.
▷ 프림의 최소 스패닝 트리 알고리즘 등이 너비 우선 탐색을 골격으로 하고 있습니다.
▷ 위의 그림을 너비 우선 탐색을 사용하면 H 0(단계) H 1 (단계) - 》 H 2 (단계)
▷ k단계에 방문하는 정점들은 시작점으로부터 최단거리가 k 입니다. (H 0(단계) : 0단계, H 1 (단계) : 1단계, H 2 (단계) : 2단계
▷ 최단거리는 이동하는 데 필요한 최소 개수의 간선으로 보면됩니다.
▷ 각 정점을 방문할 때마다 모든 인접 정점들을 검사합니다. 이 중 처음 보는 정점을 발견하면 방문 예정이라고 기록해 둔 뒤, 모든 인접 정점을 검사한 후 방문하게 됩니다.
▶ 너비 우선 탐색 구현할 경우 : 큐 (Queue)의 성질 활용
※ DFS : 스택(Stack ), BFS : 큐(Queue ) 를 사용합니다.
▷ 큐에 넣을 때 방문했다고 체크해야 한다. (discovered[])
② 너비 우선 탐색으로 그래프 순회
1번 노드 부터 시작하겠습니다.
▷현재 정점 : 1
▷순서 : 1
▷큐 : 1
1번 노드와 인접한 2번,3번 노드 큐에 담깁니다.
▷현재 정점 : 1
▷순서 : 1 2 3
▷큐 : 1 2 3
2번 노드와 인접한 4번,5번 노드 큐에 담깁니다.
▷현재 정점 : 2
▷순서 : 1 2 3 4 5
▷큐 : 2 3 4 5
3번 노드와 인접한 6번,7번 노드 큐에 담깁니다.
▷현재 정점 : 3
▷순서 : 1 2 3 4 5 6 7
▷큐 : 3 4 5 6 7
3번 코드를 큐에서 꺼낸 후 다음으로 거리가 먼 4,5,6,7 노드 순으로 탐색이 이루어집니다.
③ BFS 관련 알고리즘 문제
※ 코드 보기 를 누르시면 제가 해결한 코드를 보실 수 있습 니다.
(백준 2178) 미로 탐색 (https://www.acmicpc.net/problem/ 2178)
[설명]
▷ (1,1)에서 (N,M) 으로 가는 가장 빠른 길을 구하는 문제
▷ DFS 탐색으로는 문제를 풀 수 없고, BFS 탐색을 사용해야 한다.
코드 보기 (백준 2178) 코드 접기 (백준 2178)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Pair {
int x;
int y;
Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
public static final int[] dx = {0,0,1,-1};
public static final int[] dy = {1,-1,0,0};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
sc.nextLine();
int[][] a = new int[n][m];
for(int i = 0; i < n; i++) {
String s = sc.nextLine();
for(int j = 0; j < m; j++) {
a[i][j] = s.charAt(j) - '0';
}
}
int[][] b = new int[n][m];
boolean[][] check = new boolean[n][m];
Queue<Pair> q = new LinkedList<Pair>();
q.add(new Pair(0,0));
b[0][0] = 1;
check[0][0] = true;
while(!q.isEmpty()) {
Pair p = q.remove();
int x = p.x;
int y = p.y;
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && ny >= 0 && nx < n && ny < m) {
if(!check[nx][ny] && a[nx][ny] == 1) {
q.add(new Pair(nx, ny));
b[nx][ny] = b[x][y] + 1;
check[nx][ny] = true;
}
}
}
}
System.out.println(b[n-1][m-1]);
}
}
코드 접기 (백준 2178)
(백준 7576) 토마토 (https://www.acmicpc.net/problem/ 7576)
[설명]
▷ BFS를 활용해 몇일 후에 토마토가 모두 익는지 구하는 문제
▷ 문제에서 주어진 n, m을 행, 열에 맞춰 선언해주는 것에 주의하자.
▷ 초반 dist[i][j] = -1;로 초기화 해주는 것이 핵심이다. 어차피 최단 거리가 r인 익은 토마토는 모두 값이 갱신되기 때문입니다.
코드 보기 (백준 7576) 코드 접기 (백준 7576)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Pair {
int x;
int y;
Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
public static final int[] dx = { 0, 0, 1, -1 };
public static final int[] dy = { 1, -1, 0, 0 };
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int[][] a = new int[n][m];
int[][] dist = new int[n][m];
Queue<Pair> q = new LinkedList<Pair>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
a[i][j] = sc.nextInt();
dist[i][j] = -1;
if (a[i][j] == 1) {
q.add(new Pair(i, j));
dist[i][j] = 0;
}
}
}
while (!q.isEmpty()) {
Pair p = q.remove();
int x = p.x;
int y = p.y;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
if (a[nx][ny] == 0 && dist[nx][ny] == -1) {
q.add(new Pair(nx, ny));
dist[nx][ny] = dist[x][y] + 1;
}
}
}
}
int answer = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (answer < dist[i][j]) {
answer = dist[i][j];
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == 0 && dist[i][j] == -1) {
answer = -1;
}
}
}
System.out.println(answer);
}
}
코드 접기 (백준 7576)
( 백준 2146) 다리 만들기 (https://www.acmicpc.net/problem/ 2146)
[설명]
▷ BFS + DFS를 활용하는 문제
▷ 위의 두 문제를 풀면 해결할 수 있습니다.
▷ DFS를 활용해 섬의 번호를 만들고 BFS를 활용해 섬끼리의 최단거리를 구해 답을 내었습니다.
코드 보기 (백준 2146) 코드 접기 (백준 2146)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Pair {
int x;
int y;
Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
public static final int[] dx = {0,0,1,-1};
public static final int[] dy = {1,-1,0,0};
public static int[][] inputAry;
public static int[][] group;
public static int[][] dist;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
inputAry = new int[n][n];
//섬의 번호가 매겨져 저장된 2차원 배열
group = new int[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
inputAry[i][j] = sc.nextInt();
}
}
int cnt = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(inputAry[i][j] == 1 && group[i][j] == 0) {
dfs(i,j,n,++cnt);
}
}
}
int answer = Integer.MAX_VALUE;
for(int i = 1; i <= cnt; i++) {
answer = Math.min(answer, bfs(i, n));
}
System.out.println(answer);
}
public static void dfs(int x, int y, int n, int cnt) {
group[x][y] = cnt;
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && ny >= 0 && nx < n && ny < n) {
if(inputAry[nx][ny] == 1 && group[nx][ny] == 0) {
dfs(nx,ny,n,cnt);
}
}
}
}
// 반환값 : 섬 번호가 cnt일 때, 나머지 섬들에 다리를 놓을 때 최단 거리
public static int bfs(int cnt, int n) {
Queue<Pair> q = new LinkedList<Pair>();
dist = new int[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
//현재 섬의 번호가 cnt일 때는 거리에 0을 넣어주고, 다른 섬일 때는 -2, 그리고 바다 일때는 -1
if(group[i][j] == cnt) {
dist[i][j] = 0;
q.add(new Pair(i,j));
} else if (group[i][j] == 0) {
dist[i][j] = -1;
} else {
dist[i][j] = -2;
}
}
}
int min = Integer.MAX_VALUE;
while(!q.isEmpty()) {
Pair p = q.remove();
int x = p.x;
int y = p.y;
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && ny >= 0 && nx < n && ny < n) {
// cnt번의 섬에서 다른 섬에 접근되었을 때 타게 되는 분기
// dist[x][y]에 최단거리가 담기므로 이전 다리길이와 비교해 최소값을 갱신해준다
if(dist[nx][ny] == -2) {
min = Math.min(min, dist[x][y]);
continue;
} else if(dist[nx][ny] == -1) {
q.add(new Pair(nx,ny));
dist[nx][ny] = dist[x][y] + 1;
}
}
}
}
return min;
}
}
코드 접기 (백준 2146)
참고
프로그래밍 대회에서 배우는 알고리즘 문제해결전략 https://kks227.blog.me/220769870195
