7576 - 토마토(G5)

1. 문제

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

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

2. 풀이

전형적인 BFS 탐색 문제이다. 기저조건인 맵 바깥과, 썩은 토마토 -1을 배제하고,
나머지 토마토(0)의 영역에 익는 데까지 걸리는 시간을 매핑하였다.

이후 완전탐색으로 0이 있다면 -1 출력을, 아니라면 최대 익기까지 걸리는 시간을 탐색한다.

3. 코드

import java.util.*;
import java.io.*;

public class BOJ_7576_토마토_G5 {
	static final int D = 4; //4방탐색
	static int N, M, res = -1;
	static int[][] map;
	static boolean[][] visit;
	static Queue<Pos> q = new ArrayDeque<>(); //BFS
	static int d[][] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
	
	public static void main(String[] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		visit = new boolean[N][M];
		
		//맵 입력받기
		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] == 1) q.offer(new Pos(i, j, 1));
			}
		}
		
		//메인 메서드
		solve();
		
		//출력
		System.out.println(res);
	}

	
	private static void solve() {
		//BFS 돌려보고 빈칸 있다면 전부 전파되지 않은 것임
		//완전탐색 후 최대 값 = 걸리는 시간이므로 이를 출력
		
		//1. BFS
		while(!q.isEmpty()) {
			Pos temp = q.poll();
			int r = temp.r;
			int c = temp.c;
			int day = temp.day;
			
			if(visit[r][c]) continue;
			visit[r][c] = true;
			
			map[r][c] = Math.max(map[r][c], day);
			
			
			for (int i = 0; i < D; i++) {
				int nr = r + d[i][0];
				int nc = c + d[i][1];
				if(cantGo(nr, nc) || map[nr][nc] == -1) continue; //기저조건
				q.offer(new Pos(nr, nc, day + 1));
			}
			
		}
		
		//2. 탐색
		int max = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(map[i][j] == 0) return; //전파 실패 : -1 그대로 출력
				if(map[i][j] > 0) max = Math.max(max, map[i][j]);
			}
		}
		res = max - 1;
	}

	static boolean cantGo(int r, int c) {
		if(r < 0 || c < 0 || r >= N || c >= M) return true;
		return false;
	}
	static class Pos {
		int r, c, day;

		public Pos(int r, int c, int day) {
			super();
			this.r = r;
			this.c = c;
			this.day = day;
		}
	}
}