[BOJ]7569_토마토_Java

--문제--

www.acmicpc.net/problem/7569

7569번: 토마토

--문제 접근--

이문제는 BFS의 대표적인 문제로 하루가 지날 때마다 토마토의 주변 상하좌우+ 토마토의 위쪽, 토마토의 아래쪽을 전부 익는 걸로 판단합니다.

여기서 주의해야 할 점은 하루에 하는 양을 일시적으로 지정해두고 그만큼 돌게 하는 것이고, 2차원 배열로 풀 때에는 입력을 볼 때는 가능할 것 같지만 

2 2 2
-1 -1
1 -1
0 -1
-1 -1

이러한 반례를 해결하지 못해 3차원을 사용하여 문제를 풀었습니다.

1. 입력을 받을 때에 토마토를 발견한다면 바로바로 queue에 넣습니다.

2.bfs를 실행시켰을 때에 하루의 양만큼 돌게 하기 위해 for문을 사용합니다.

3.for문을 돌면서 queue를 집어넣는다면 그것은 하루를 소비한 것이라고 판단하여 boolean값을 true로 바꿔주고 for문이 끝난 이후 boolean값이 true라면 하루를 추가합니다.

--코드--

package 백준문제풀이;

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

public class BOJ_7569토마토 {
	static int[] dr= {-1,1,0,0,0,0};
	static int[] dc= {0,0,-1,1,0,0};
	static int[] dz= {0,0,0,0,1,-1};
	static int row,column,num;
	static int[][][] map;
	static boolean[][][] visit;
	static Queue<int[]> queue=new LinkedList<>();
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		column=sc.nextInt();
		row=sc.nextInt();
		num=sc.nextInt();//3차원임을 생각하기
		map=new int[num][row][column];
		visit=new boolean[num][row*num][column];
		for(int k=0;k<num;k++) {
			for(int i=0;i<row;i++) {
				for(int j=0;j<column;j++) {
					map[k][i][j]=sc.nextInt();
					if(map[k][i][j]==1)queue.add(new int[] {i,j,k});//토마토를 발견한다면 queue에 넣기.
				}
			}
		}
		
		int answer=bfs();
		boolean check=false;
		out:for(int k=0;k<num;k++) {//bfs를 통해 토마토를 전파했는데도 아직 안익은 토마토가 있는지 확인하는 작업
			for(int i=0;i<row;i++) {
				for(int j=0;j<column;j++) {
					if(map[k][i][j]==0) {
						check=true;
						break out;//out을 통해  0이발견된다면 한번에 나가기 위해서 이러한 것을 사용
					}
					
				}
			}
		}
		if(check)System.out.println(-1);//0이 존재한다면 -1출력
		else System.out.println(answer);//check가 false라면 그것은 다 0이없다고 판단하여 정상적으로 출력
		
		
	}
	static int bfs() {
		int ans=0;
		while(true) {
			int temp=queue.size();//사이즈만큼 하는 이유는 전체를 하는게 레벨노드처럼 하루의 양을 지정해놓고 하기 위해 size를 사용합니다		
			boolean value=false;
			for(int i=0;i<temp;i++) {
				int[] curr=queue.poll();
				visit[curr[2]][curr[0]][curr[1]]=true;//bfs를 사용하면 바로 방문체크하고 시작
				for(int d=0;d<6;d++) {
					int dx=curr[0]+dr[d];
					int dy=curr[1]+dc[d];
					int dz1=curr[2]+dz[d];
					if(dx>=0&&dy>=0&&dx<row&&dy<column&&dz1>=0&&dz1<num&&visit[dz1][dx][dy]==false&&map[dz1][dx][dy]==0) {
						value=true;
						map[dz1][dx][dy]=1;
						queue.add(new int[] {dx,dy,dz1});
					}
				}
			}
			if(value)ans++;//하루가 지났는데 토마토가 바뀐게 있다면 그것을 하루를 소비해서 할만한 가치가 있어서 바로ans 에 플러스 1
			if(queue.isEmpty())break;//queue가 비어있다면 더이상 할것이없다는 것이므로 탈출
		}
		return ans;
	}
}