백준 : 7576 (토마토/2차원배열) (BFS)

이문제는 7569(토마토/3차원배열)를 푼 다음에 풀었기때문에 쉽게 풀수 있었다.

 

3차원 배열이었던것을 단순하게 2차원으로만 수정해주면 끝!!!

import java.util.*;

class Node {
	private int x;
	private int y;

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

	public int getX() {
		return this.x;
	}

	public int getY() {
		return this.y;
	}
}

class Main {

	static int n, m, resultCnt = 0;
	static boolean[][] visited = new boolean[n][m];
	static int[][] day = new int[n][m];
	static int[][] graph = new int[n][m];
	static int[] dx = { -1, 1, 0, 0, 0, 0 }; // 앞,뒤,좌,우
	static int[] dy = { 0, 0, -1, 1, 0, 0 };
	static Queue<Node> q = new LinkedList<>(); // 시작점이 여러개 이므로 static으로 세팅*****

	public static void bfs() {
		while (!q.isEmpty()) {
			Node nowNode = q.poll(); // 삭제
			int xi = nowNode.getX();
			int yi = nowNode.getY();

			for (int i = 0; i < 6; i++) {
				int nx = xi + dx[i];
				int ny = yi + dy[i];

				if (nx < 0 || nx >= n || ny < 0 || ny >= m)
					continue; // 범위

				if (graph[nx][ny] == 0 && visited[nx][ny] == false) { // 0일때만 익을 수 있다.
					q.offer(new Node(nx, ny));
					visited[nx][ny] = true;
					day[nx][ny] = day[xi][yi] + 1;// 날짜 카운트*****

					resultCnt = resultCnt < day[nx][ny] ? day[nx][ny] : resultCnt; // 날짜 그래프중 가장큰값 세팅*****
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		m = sc.nextInt(); // 가로 -> y
		n = sc.nextInt(); // 세로 -> x
		sc.nextLine(); // 버퍼

		// 초기화
		visited = new boolean[n][m];
		day = new int[n][m];
		graph = new int[n][m];

		// 그래프 입력

		for (int i = 0; i < n; i++) {
			String st = sc.nextLine();
			String[] stArr = st.split(" ");

			for (int j = 0; j < m; j++) {
				int input = Integer.parseInt(stArr[j]);
				graph[i][j] = input;

				if (input == -1) { // 감이 없는자리는 방문한것으로 정한다.
					visited[i][j] = true;
				}
			}
		}

		// DFS
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (graph[i][j] == 1 && visited[i][j] == false) { // 방문안한 익은 감인경우*****
					q.offer(new Node(i, j)); // 삽입, 시작점이 같은 것들을 먼저 큐에 삽입하고 BFS 시작*****
					day[i][j] = 0; // 시작점은 날짜 0으로 시장
					visited[i][j] = true; // 방문표시
				}
			}
		}

		bfs();

		// 모두 1이 아닐때 -1
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (graph[i][j] == 0 && visited[i][j] == false) { // 방문안한 안익은 감이있다
					resultCnt = -1;
				}
			}
		}

		System.out.println(resultCnt);

	}
}