[백준] 7569 토마토 - BFS

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

7569번: 토마토

 

 

문제풀이

일반적이 BFS문제입니다.

다만, 높이가 들어가서 3차원 배열을 사용해야한다는점이 낯설었던 문제입니다.

또한 입력값이 크기에 BufferedReader를 사용하여 진행합니다.

 

- 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 

: 이 조건에 보면 M은 상자의 가로 칸의 수이고, N은 상자의 세로칸입니다.

그러므로 배열 값을 설정할때

int[][][] map = new int[H][N][M] 이런식으로 N을 세로칸의수, M을 가로칸의 수로 사용합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	
	public static int M,N,H, result;
	public static int[][][] map;
	public static Queue<Node> q = new LinkedList<>();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	M = Integer.parseInt(st.nextToken());
    	N = Integer.parseInt(st.nextToken());
    	H = Integer.parseInt(st.nextToken());
    	
    	map = new int[H][N][M];
    	
    	for(int i=0;i<H;i++) {
    		for(int j=0;j<N;j++) {
    			st = new StringTokenizer(br.readLine());
    			for(int k=0;k<M;k++) {
    				map[i][j][k] = Integer.parseInt(st.nextToken());
    				if(map[i][j][k] == 1) q.add(new Node(i,j,k,0));
    			}
    		}
    	}
    	
    	BFS();
    	for(int i=0;i<H;i++) {
    		for(int j=0;j<N;j++) {
    			for(int k=0;k<M;k++) {
    				if(map[i][j][k] == 0) {
    					System.out.println("-1");
    					return ;
    				}
    					
    			}
    		}
    	}
    	System.out.println(result);
    }
    
    public static void BFS() {
    	int[] dx = {-1,1,0,0,0,0};
    	int[] dy = {0,0,-1,1,0,0};
    	int[] dh = {0,0,0,0,-1,1};
    	
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int h = temp.h;
    		int r = temp.r;
    		int c = temp.c;
    		int cnt = temp.cnt;
    		result = cnt;
    		for(int dir = 0; dir < 6; dir++) {
    			int nr = r + dx[dir];
    			int nc = c + dy[dir];
    			int nh = h + dh[dir];
    			if(nh < 0 || nh >= H || nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
    			if(map[nh][nr][nc] == 1 || map[nh][nr][nc] == -1) continue;
    			q.offer(new Node(nh, nr, nc, cnt + 1));
    			map[nh][nr][nc] = 1;
    		}
    	}
    }
    
}
 
class Node{
	int h; //height
	int r; //row
	int c; //col
	int cnt;
	public Node(int h, int r, int c, int cnt) {
		this.h = h;
		this.r = r;
		this.c = c;
		this.cnt = cnt;
	}
}