[백준/Java] 7576: 토마토

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

 

조건

• TimeLimit = 1s
• 하루 뒤에, 익은 토마토의 상하좌우 안익은 토마토가 익는다
• 토마토가 모두 익는 최소 일수를 구하라. 단, 모두 익지 못하면 -1을 출력하라
• M,N은 1000이하, 1은 익은 토마토, 0은 익지 않은 토마토, -1은 빈공간이다

 

풀이

• 완전탐색 -> 최소 시간/거리를 구해야하므로 BFS 사용
  • 상하좌우를 탐색하는 BFS의 시간복잡도는 O(4*V^2) ~= O(V^2)이므로, 최대 O(100만)으로 해결 가능

 

코드

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

public class Main {

	static int n;
	static int m;
	static int[][] map;
	static List<Node> ripe = new ArrayList<>();
	static int minTime = Integer.MAX_VALUE;
	static int cntNoRipe = 0;
	static int[] dr = { -1, 1, 0, 0};
	static int[] dc = { 0, 0, -1, 1};


	public static void main(String[] args) throws IOException {

		// input
		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];
		for (int i=0; i<n; i++) {

			int[] row = Arrays.stream(br.readLine().split(" "))
				.mapToInt(Integer::parseInt)
				.toArray();

			map[i] = row;

			for (int j=0; j<m; j++) {

				if (row[j] == 1) ripe.add(new Node(i, j, 0));
				else if (row[j] == 0) cntNoRipe ++;

			}
		}

		// bfs
		bfs();

		// result
		System.out.print(cntNoRipe != 0 ? -1 : minTime);
	}





	static void bfs() {

		// set-up
		Deque<Node> q = new ArrayDeque<>(ripe);

		// search
		int lastTime = 0;
		while (!q.isEmpty()) {

			Node cur = q.pop();
			int r = cur.r;
			int c = cur.c;
			int t = cur.t;

			lastTime = t;

			for (int i=0; i<4; i++) {

				int nr = r + dr[i];
				int nc = c + dc[i];

				// validate
				if (nr<0 || nr>=n || nc<0 || nc>=m) continue;
				if (map[nr][nc] != 0) continue;

				map[nr][nc] = 1;
				cntNoRipe --;
				q.add(new Node(nr, nc, t+1));

			}
		}

		minTime = Math.min(minTime, lastTime);
	}


	static class Node {

		int r;
		int c;
		int t;

		Node(int r, int c, int t) {
			this.r = r;
			this.c = c;
			this.t = t;
		}

	}

}