Menu

Subscribe

[JAVA/백준] DFS와 BFS: 토마토

HEESOO on Boj

👀 문제

https://www.acmicpc.net/problem/7569

👊 도전

1. 설계

  1. 토마토가 익는 최소 일수를 구해야하므로 BFS를 사용한다.
  2. 익은 토마토의 위치를 큐에 넣은 후, 하나씩 빼서 덜 익은 토마토로 위아래상하좌우 이동(큐에 삽입)한다.

2. 구현 (성공 코드)

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
71
72
73
74
75
76

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @author HEESOO
 *
 */
class Node{
	int x;
	int y;
	int z;
	public Node(int x, int y, int z) {
		this.x=x;
		this.y=y;
		this.z=z;
	}
}
public class Main {
	static int m,n,h,zero;
	static int[][][] map;
	static boolean[][][] visit;
	public static int bfs(Queue<Node> q) {
		int[] dotX= {0,0,0,0,-1,1};
		int[] dotY= {0,0,1,-1,0,0};
		int[] dotZ= {1,-1,0,0,0,0};
		int cnt=0;
		while(!q.isEmpty()) {
			Node node=q.poll();
			cnt=map[node.x][node.y][node.z]+1;
			for(int i=0;i<6;i++) {
				int xx=node.x+dotX[i];
				int yy=node.y+dotY[i];
				int zz=node.z+dotZ[i];
				if(0<=xx&&xx<n&&0<=yy&&yy<m&&0<=zz&&zz<h) {
					if(map[xx][yy][zz]!=-1&&!visit[xx][yy][zz]) {
						visit[xx][yy][zz]=true;
						map[xx][yy][zz]=cnt;
						zero--;
						q.offer(new Node(xx,yy,zz));
					}
					
				}
			}
		}
		if(zero!=0) return -1;
		else return cnt-2;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		m=scan.nextInt();
		n=scan.nextInt();
		h=scan.nextInt();
		map=new int[n][m][h];
		visit=new boolean[n][m][h];
		Queue<Node> q=new LinkedList<>();
		zero=0;
		for(int i=0;i<h;i++) {
			for(int j=0;j<n;j++) {
				for(int k=0;k<m;k++) {
					map[j][k][i]=scan.nextInt();
					if(map[j][k][i]==0) zero++;
					else if(map[j][k][i]==1) {
						q.offer(new Node(j, k, i));
						visit[j][k][i]=true;
					}
				}
			}
		}
		
		System.out.println(bfs(q));
	}
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. BFS를 구현한다
    • 최소 일수를 구해야하므로 BFS를 사용한다.
    • 큐에 익은 토마토의 위치를 클래스 Node를 통해 모두 저장한다. 하나만 저장하고 while문을 시작하지 않도록 한다. 익은 토마토가 여러 개일 경우 중간 지점에서 만날 수 있으므로 계속 확인해야하기 때문이다.
    • zero 변수를 두어 덜 익은 토마토가 몇 개인지 확인한다. 토마토가 모두 익지 못할 경우를 확인하기 위함이다. 실행결과
    • 현재 노드에서 움직일 수 있는 방향은 총 여섯개이다. 6가지 경우를 확인하여 토마토에 영향을 줄 수 있는지 확인한다. 덜 익은 토마토를 익게 만들 수 있다면 그 노드를 큐에 저장하고, visit값을 true로 바꾸고, zero–하여 덜 익은 토마토를 하나 줄이고, map에는 그 토마토가 익기위해 걸리는 일수를 저장한다.
    • while문을 다 돌면 BFS탐색이 끝난 것이므로, zero값을 확인하여 덜 익은 토마토가 있는지 확인한다. zero!=0이면 토마토를 모두 익힐 수 없으므로 -1을 리턴하고, zero==0이라면 모두 익은 것이므로 cnt-2를 리턴한다(map에서 0부터 시작해야하는데 1부터 했으므로 -1, while문에서 cnt저장을 위해 cnt+1했으므로 -1).

👏 해결 완료!