백준 : 7569 (토마토/3차원배열) (BFS)

이번문제는 풀면서 꽤나 애먹었던 문제이다.

 

이문제를 풀면서 주의해야할 점에 대해 알아보기로 하자.

 

1. 3차원 배열

2. Node에서 변수 선언시 static 사용하지 않기 -> 변수가 공유되면 안됨.

3. 시작점이 여러개인 경우 Queue를 static으로 선언하고, 여러개의 시작점을 큐에 삽입 후 BFS 실행한다.

4. 그래프, 방문그래프, 날짜그래프 총 3개의 그래프를 이용한다.

 

1,3번의 경우 처음 접해보는 방식이기에 풀고나서 한층 더 보는 눈높이가 높아진거 같아서 기쁘다.

package com.controller;

import java.util.*;

class Node {
	private int h; //static안붙이도록 주의*****
	private int x;
	private int y;

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

	public int getH() {
		return this.h;
	}

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

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

class Main {

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

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

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

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

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

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

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

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

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

		// 그래프 입력
		for (int x = 0; x < h; x++) { 
			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[x][i][j] = input;

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

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

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

		System.out.println(resultCnt);

	}
}