[백준] 7576번:토마토 (Java 자바)

문제

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

7576번: 토마토

 

풀이 및 소스코드

 

7달 전과 달리 한 번에 맞췄당 ㅎㅎㅎ

 

토마토문제는 며칠이 지나서 다 익는지, 시간을 출력해야 하기 때문에 시간의 구분(?) 이 중요하다.

나는 bfs로 풀었다.

처음에 익은 토마토의 좌표를 큐에 넣고, 사방탐색을 해주면서 큐에 계속 자식의 좌표가 들어가기 때문에 시간 구분이 애매하게 된다.

자식의 좌표를 넣기 전, 현재 큐의 크기를 변수에 넣고, 그 크기만큼 돌아갔을 때 1의 시간이 지났다는 것만 고려해주면 된다. 

 

4개의 좌표가 처음에 큐에 들어옴 -> 4개의 좌표를 bfs 돌리면서 8개의 자식 좌표가 큐에 들어옴 -> 4개의 반복문이 끝나면 시간 1이 흐른 것. -> 8개의 반복문이 끝나면 시간 1이 또 흐른 것  !!!!

 

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

class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		int m = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());
		int[][] map = new int[n][m];
		Queue<node> q = new LinkedList<node>();
		//익은 토마토가 들어갈 큐
		int cnt = 0; //빈칸의 개수 저장
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
				if(map[i][j]==0) cnt++;
				else if(map[i][j]==1) q.add(new node(i,j));
			}
		}
		if(cnt==0) {
			System.out.println("0");
			System.exit(0);
		}
		
		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1};
		int res = 1;
		while(!q.isEmpty()) {
			int qn = q.size();
			for(int qq=0;qq<qn;qq++) {
				int x = q.peek().x;
				int y = q.peek().y;
				q.poll();
				for(int i=0;i<4;i++) {
					int nowx = x+dx[i], nowy = y+dy[i];
					if(0>nowx||0>nowy||n<=nowx||m<=nowy) continue;
					if(map[nowx][nowy]==0) {
						map[nowx][nowy] = 1;
						cnt--;
						q.add(new node(nowx,nowy));
					}
				}
			}
			if(cnt==0) {
				System.out.println(res);
				System.exit(0);
			}
			res++;
		}
		System.out.println("-1");
		
	}
}
class node{
	int x,y;

	public node(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
	
}