큐를 이용해서 구현하며, 기본적인 BFS 탐색 순서는 다음과 같다.
1. 큐를 하나 만든다
2. 시작할 노드를 넣는다
3. 시작할 노드를 꺼내고 출력한다
4. 인접한 노드를 큐에 넣는다
5. 이 때, 한번 큐에 넣었던 노드는 다시 큐에 넣지 않아야 한다
BFS 관련된 문제로 소스코드로 확인해보자
백준 토마토 문제이다.
https://www.acmicpc.net/problem/7569
7569번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,
www.acmicpc.net
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main{
public static int N, M, H;
public static int[][][] box;
public static int[] dx = {1, -1, 0, 0, 0, 0};
public static int[] dy = {0, 0, 1, -1, 0, 0};
public static int[] dz = {0, 0, 0, 0, 1, -1};
public static Queue<Tomato> queue = new LinkedList<Tomato>();
static class Tomato {
int x, y, z;
public Tomato(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken()); /** 1번 문제는 변수 H를 1로 주면 해결된다.. */
box = new int[H][N][M];
for (int k = 0; k < H; k++) {
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < M; j++) {
box[k][i][j] = Integer.parseInt(st.nextToken());
if(box[k][i][j] == 1){
queue.offer(new Tomato(i, j, k));
}
}
}
}
bfs();
}
static int isPerfectlyRipe () {
int max = -10000000;
for (int k = 0; k < H; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (box[k][i][j] == 0) {
return 0;
}
max = max > box[k][i][j] ? max : box[k][i][j];
}
}
}
return max;
}
public static void bfs() {
while (!queue.isEmpty()) {
Tomato tomato = queue.poll(); // 큐에서 익은 토마토를 하나 꺼내자
for (int i = 0; i < 6; i++) { // 상하좌우위아래 6개 방향으로 이동했을 때의 각 토마토 확인
int _x = tomato.x + dx[i];
int _y = tomato.y + dy[i];
int _z = tomato.z + dz[i];
if(0 <= _x && _x < N &&
0 <= _y && _y < M &&
0 <= _z && _z < H) { // 이동한 장소가 배열의 크기를 벗어나지 않도록 해야한다
if (box[_z][_x][_y] == 0) { // 아직 안익었다면 큐에 넣어준다
box[_z][_x][_y] = 1; //이제 익었으니까 1로 변환해주어야 다음 탐색을 이어나갈 수 있다
queue.add(new Tomato(_x, _y, _z));
box[_z][_x][_y] = box[tomato.z][tomato.x][tomato.y] + 1; // 날짜정보를 저장해준다 이 정보는 1부터 시작했으니 결과에서 1을 빼주어야한다
}
}
}
}
System.out.println(isPerfectlyRipe() - 1);
}
}
'Develop Issue > Algorithm' 카테고리의 다른 글
| 선택, 삽입, 버블정렬에 대한 설명과 소스코드 (455) | 2017.06.12 |
|---|