[백준(Baekjoon)][자바(java)] 7576 : 토마토 / 그래프와 순회

 

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

7576번: 토마토

 

문제 풀이

 

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 Main {

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken()),
			N = Integer.parseInt(st.nextToken()),
			map[][] = new int[N][M], val, i, j,
			cnt_total = N * M;
		boolean visited[][] = new boolean[N][M];
		Queue<int[]> queue = new LinkedList<>(); // x, y, d(distance)
		for (i = 0; i < N; ++i) {
			st = new StringTokenizer(br.readLine());
			for (j = 0; j < M; ++j) {
				val = Integer.parseInt(st.nextToken());
				map[i][j] = val;
				if (val == 1) {
					visited[i][j] = true;
					queue.add(new int[]{i, j, 0});
				}
				if (val == -1)
					cnt_total--;
			}
		}
		br.close();
		
		cnt_total -= queue.size();

		final int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}, n = dx.length;
		int cnt = 0, pos[], x, y, d, nx, ny, nd, answer = 0;
		loop:
		while (!queue.isEmpty()) {
			pos = queue.remove();
			x = pos[0];
			y = pos[1];
			d = pos[2];
			nd = d + 1;
			for (i = 0; i < n; ++i) {
				nx = x + dx[i];
				ny = y + dy[i];
				if (nx < 0 || nx >= N || ny < 0 || ny >= M || 
					visited[nx][ny] || map[nx][ny] == -1)
					continue;
				cnt++;
				if (cnt == cnt_total) {
					answer = nd;
					break loop;
				}
				map[nx][ny] = 1;
				visited[nx][ny] = true;
				queue.add(new int[]{nx, ny, nd});
			}
		}

		System.out.println(cnt == cnt_total ? answer : -1);
	}
}