백준 BOJ 7576 토마토 [자바]

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

7576번: 토마토

문제 분석

상자에 토마토가 들어있다. 1은 익은 토마토, 0은 익지 않은 토마토, -1은 토마토가 없는 상태.

익은 토마토는, 하루마다 상하좌우의 토마토를 익힐 때,

토마토가 다 익을려면 몇일이 걸리는지 출력해라.

단, 다 익지 못하는 상황일 때는 -1 출력

 

상자의 크기 m, n (m이 가로)

n줄에 걸쳐서 들어있는 토마토의 상태 입력.

 

 

문제 풀이

location이라는 멤버클래스를 하나 생성.

이 클래스에는 위치정보(r, c) 두 int값이 들어감.

 

처음에 입력을 받을 때, 0의 수를 세 놓음.

위 클래스를 인자로 갖는 큐를 선언하고,

이 큐에 최초 익어있는 토마토의 위치를 다 넣음.

여기서 하나씩 꺼내면서, 그 주변의 안익은 토마토를 익히고, 0의 수를 하나 빼고, 이 위치를 큐에 넣음, 이를 반복.

 

큐가 비었을 때. 0의 수가 0이면 소요된 day를 출력. 아니면 -1을 출력

 

전체 코드

package ChangHangeol;

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

public class BJ7576_토마토 {
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
		
	public static void main(String[] args) throws IOException {
		class location {
			int r;
			int c;
			public location(int r, int c) {
				this.r = r;
				this.c = c;
			}
		}
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Queue<location> que = new LinkedList<location>();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int C = Integer.parseInt(st.nextToken());
		int R = Integer.parseInt(st.nextToken());
		
		int[][] box = new int[R][C];
		int count0 = 0;
		for(int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < C; j++) {
				box[i][j] = Integer.parseInt(st.nextToken());
				if(box[i][j] == 0) count0++;
				else if(box[i][j] == 1) que.add(new location(i, j));
			}
		}
		int day = 0;
		while(!que.isEmpty()) {
			day++;
			//이전 날에 입력된 토마토 주변 익히기
			int size = que.size();
			for(int t = 0; t < size; t++) {
				location tomato = que.poll();
				
				for(int d = 0; d < 4; d++) {
					int nr = tomato.r + dr[d];
					int nc = tomato.c + dc[d];
					
					if(nr >= 0 && nr < R && nc >= 0 && nc < C && box[nr][nc] == 0) {
						count0--;
						box[nr][nc] = 1;
						que.add(new location(nr, nc));
					}
				}
			}
		}
		System.out.println((count0 == 0) ? (day-1) : -1);
	}
}

 

 

++

한번에 통과했을 때의 이 쾌감이란~~ 크으