[백준] 7576번 - 토마토

 

BFS를 이용한 탐색문제이다. 이 문제의 경우, 기존에는 각 좌표에 해당하는 visited 배열을 통해서 방문 여부를 판단하였는데, 그렇게 하지 않고 다음 좌표를 방문할 때, count값을 1 증가시키는 방식으로 진행하였다.

처음에 값이 1인 좌표를 찾고, 그 좌표를 시작으로 상하좌우의 값들을 범위가 맞는지와 값이 0인지 유무를 판단하여 0인 경우 큐에 저장하고, 계속 탐색을 진행한다. 이 때 큐에 저장 시 하루가 지난 것으로 판단하므로 count값을 1 증가시켜주고, 모든 탐색이 끝났을 때, 0이 존재하면 -1을, 그렇지 않은 경우는 count값을 출력하도록 하였다.

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 class Node {
		int x;
		int y;
		int cnt;

		Node(int x, int y, int cnt) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}
	}

	public static int[] nx = { -1, 0, 0, 1 };
	public static int[] ny = { 0, 1, -1, 0 };
	public static int[][] ary;
	public static int x;
	public static int y;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		y = Integer.parseInt(st.nextToken());
		x = Integer.parseInt(st.nextToken());

		ary = new int[x][y];

		for (int i = 0; i < x; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < y; j++) {
				ary[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		bfs();
	}

	public static void bfs() {
		Queue<Node> q = new LinkedList<>();
		int cnt = 0;

		for (int i = 0; i < x; i++) {
			for (int j = 0; j < y; j++) {
				if (ary[i][j] == 1) {
					Node n = new Node(i, j, 0);

					q.add(n);
				}
			}
		}

		while (!q.isEmpty()) {
			Node node = q.poll();
			cnt = node.cnt;
			
			for (int i = 0; i < 4; i++) {
				int X = node.x + nx[i];
				int Y = node.y + ny[i];

				if (X >= 0 && X < x && Y >= 0 && Y < y) {
					if (ary[X][Y] == 0) {
						ary[X][Y] = 1;
						q.add(new Node(X, Y, cnt + 1));
					}
				}
			}
		}
		for (int i = 0; i < x; i++) {
			for (int j = 0; j < y; j++) {
				if (ary[i][j] == 0) {
					System.out.println(-1);
					return;
				}
			}
		}
		System.out.println(cnt);
	}
}