[백준 - 7576번] 토마토 - 자바(JAVA) 정리 및 해설

이번시간에는 토마토 BFS 문제에 대해서 풀어보도록 하겠습니다.

이 문제는 익은 토마토가 옆의 토마토를 다음날에 익게 만들고 그 일수를 구해야하는 대표적인 문제입니다.

그럼 이 일수를 구하는데 가장 유요한 코딩전략은 BFS입니다. 왜냐하면 한박스 내에 몇개의 익은 토마토가 있는지 모르기 때문에, 1일당 각각의 익은 토마토별로 안익은 토마토를 익게 만들어야합니다.  

그렇다면 dfs로 구현하기에는 어렵기때문에 BFS를 사용해서 문제를 풀어야하겠죠. 

이미 다익은 경우와 못익히는 경우에는 출력을 다르게 해줘야하지만, 그렇게 어렵지 않으니 바로 설명해보죠.

1. 토마토처럼 x,y좌표를 통해서 위치를 판단하는 경우에는 두가지 인수를 동시에 움직여야합니다.

BFS의 경우 Queue 안에 넣어야하는데요. 물론 x값과 y값을 두 큐에 넣고 동시에 같이 뺄 수 있지만. 

사실 저는 그런건 좀 신용을 못하겠는게 혹시 큐가 꼬여서 순번이 바뀐다면이라는 무서운 상상을 하기에 저는 그냥 토마토 클래스를 만들어서 두인자를 같이 묶어줍니다.

그리고 queue의 <>인 제너릭을 통해서 tomato를 넣어서 큐에 토마토를 제외한 다른 어떤것도 넣지 않겠끔 지정을 합니다.

2. 그리고 이 박스를 순회하면서 익은 토마토를 q에다가 집어 넣습니다.  bfs방법처럼 일정한 점에서 시작할 수 없습니다. 왜냐하면, 익은 토마토가 N개라면 1일 후에는 동시에 N개의 토마토 근처의 있는 안익은 토마토를 익게끔 해줘야 하기때문에 이번 bfs는 인수를 받지 않고 실행만 시키면 알아서 작동되게 합니다.

3. 그리고 특정조건인 다익은경우는 안들어있는 박스와 익은 토마토가 동률일때 다 익었다고 판단합니다.  

그리고 난다음에 q에서 뺀다음에 map을 1로 만들어주고 상하좌우에 안익은 토마토가 있는지 확인합니다.

만약 있다면, 그 있는 토마토를 새로운 tomato 클래스로 만들어주고 큐에 넣어줍니다. 그리고 다음에는 그 이동할 장소에 

몇일이 지났는지 현재 토마토 위치의 몇일이 지났는지를 체크하는 visit[][] 변수에 +1을 해서 더합니다. 

ㄴ위의 말이 좀 헛갈리신다면 BFS에대해서 한번 더 자세히 알아봐야합니다.

왜냐하면, 결국 익게 만들면 하루가 지나있기 때문에 그 값을 늘려서 진행해줘야합니다.

그러면 이제 계속 반복되면서 q에 아무것도 안남을때까지 반복해줄겁니다.

4. 마지막으로 못익게하는 경우는 다시 이 박스를 순회하면서 0이 있는경우를 확인해서 있으면 안되게 출력하고 0이 없으면 값을 튀어 나오게 끔하면 답이 잘 나오게 될겁니다.

/* 2019.02.03 bfs
*/
package codeBaekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class tomato{
	int x; 
	int y;
	public tomato(int x, int y){
		this.x = x;
		this.y = y;
	}
}

public class no7576_tomato {
	static int m,n, cm, cp ,check=-1;
	static int map[][], visited[][];
	static int dx[] ={0,1,0,-1};
	static int dy[] = {1,0,-1,0};
	static void bfs(){
		Queue<tomato> q = new LinkedList<tomato>();
		for(int i =1; i<n+1; i++){
			for(int j=1; j<m+1; j++ ){
				if(map[i][j]==1){
					visited[i][j] =1;
					q.offer(new tomato(i, j));
					cp++;
				}
				if(map[i][j]==-1){
					cm--;
				}
			}
		}
		if(cp==cm){
			check =0;
		}
		while(!q.isEmpty()){
			tomato temp = q.poll();
			map[temp.x][temp.y] =1;
			for(int i=0; i<4; i++ ){
				if(map[temp.x+dx[i]][temp.y+dy[i]] ==0 && visited[temp.x+dx[i]][temp.y+dy[i]]==0){
					q.offer(new tomato(temp.x+dx[i], temp.y+dy[i]));
					visited[temp.x+dx[i]] [temp.y+dy[i]] = visited[temp.x][temp.y] +1;
				}
			}
			
		}
		
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String tc = br.readLine();
		StringTokenizer st = new StringTokenizer(tc, " ");
		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		map= new int[n+2][m+2];
		visited = new int[n+2][m+2];
		for(int i =0; i<n+2; i++){
			Arrays.fill(visited[i], 0);
			Arrays.fill(map[i], -1);
		}
		for(int i=1; i<n+1; i++){
			String s = br.readLine();
			StringTokenizer st1 = new StringTokenizer(s, " ");
			for(int j=1; j<m+1; j++){
				map[i][j] = Integer.parseInt(st1.nextToken());
			}
		}
		bfs();
		int max = -1;
		boolean not = true;
		for(int i =1; i<n+1; i++){
			for(int j=1; j<m+1; j++ ){
				if(map[i][j]==0){
					not = false;
				}
				max = Math.max(max, visited[i][j]);
			}
		}
		if(!not){
			System.out.println(-1);
		}
		else{
			if(check==0){
				System.out.println(0);
			}
			else{
				System.out.println(max-1);
			}
		}
	}
}