BEAKJOON / 백준 - JAVA 7569번 토마토

2024.08.11기준 - 골드5

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 익은 토마토가 안 익은 토마토를 익게 만들 때, 전부 익을 수 있다면 다 익을 때 까지 걸리는 시간을 아니라면 -1을 출력하는 문제입니다.

 

1. 우선 참조하는 위치에서 이동할 좌표를 선언했습니다.

static int[] dx = {0, 1, 0, -1, 0, 0};
static int[] dy = {-1, 0, 1, 0, 0, 0};
static int[] dh = {0, 0, 0, 0, 1, -1};

 

2. 밭을 저장할 int[][][] field을 생성했습니다.

static int[][][] field;

field = new int[h][m][n];
for (int i = 0; i < h; i++) {
    for (int j = 0; j < m; j++) {
        st = new StringTokenizer(br.readLine());

        for (int k = 0; k < n; k++) {
            field[i][j][k] = Integer.parseInt(st.nextToken());
        }
    }
}

 

3. 밭에서 익은 토마토가 있을 때, 함수를 호출 해줍니다.

for (int i = 0; i < h; i++) {
    for (int j = 0; j < m; j++) {
        for (int k = 0; k < n; k++) {
            if (field[i][j][k] == 1) { // 토마토가 익었을 때
                function(i, j, k);
            }
        }
    }
}

 

4. 함수에서는 익은 토마토로 호출되었을 때 그 좌표를 기준으로 총 6방향을 체크합니다.

1. 총 6방향을 체크하며 안 익은 토마토가 익을 때, qu에 h, x, y좌표를 추가해줍니다.
2. 추가된 좌표를 기준으로 다시 안 익은 토마토를 구해 +1을 더 해 시간을 계산을 해주는 방식으로 선택했습니다.

// 토마토가 전파를 하는 함수.
private static void function(int hi, int y, int x) {
    Queue<Integer> hq = new LinkedList<>();
    Queue<Integer> yq = new LinkedList<>();
    Queue<Integer> xq = new LinkedList<>();
    hq.add(hi);
    yq.add(y);
    xq.add(x);

    int nowh, nowy, nowx, nexth, nexty, nextx;
    while (!hq.isEmpty()) {
        nowh = hq.poll();
        nowy = yq.poll();
        nowx = xq.poll();

        // 함수를 호출한 위치에서 총 6방향을 확인합니다.
        for (int i = 0; i < 6; i++) {
            nexth = nowh + dh[i];
            nexty = nowy + dy[i];
            nextx = nowx + dx[i];

            // 익지 않은 토마토일 때
            if (check(nexth, nexty, nextx) && field[nexth][nexty][nextx] == 0) {
                field[nexth][nexty][nextx] = field[nowh][nowy][nowx] + 1;
                hq.add(nexth);
                yq.add(nexty);
                xq.add(nextx);

                // 토마토가 익었지만 더 빨리 익을 수 있을 때
            } else if (check(nexth, nexty, nextx) && field[nexth][nexty][nextx] > field[nowh][nowy][nowx] + 1) {
                field[nexth][nexty][nextx] = field[nowh][nowy][nowx] + 1;
                hq.add(nexth);
                yq.add(nexty);
                xq.add(nextx);
            }
        }
    }
}

// 참조하는 위치가 밭 안에 있는지 확인하는 함수.
private static boolean check(int hi, int y, int x) {
    return hi >= 0 && y >= 0 && x >= 0 && hi < h && y < m && x < n;
}

 

 

 

 

 

코드

package Main;

import java.io.*;
import java.util.*;

public class Main {
	
	static int[] dx = {0, 1, 0, -1, 0, 0};
	static int[] dy = {-1, 0, 1, 0, 0, 0};
	static int[] dh = {0, 0, 0, 0, 1, -1};
	static int n, m, h;
	static int[][][] field;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken()); // 열
		m = Integer.parseInt(st.nextToken()); // 행
		h = Integer.parseInt(st.nextToken()); // 높이
		
		
		field = new int[h][m][n];
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < m; j++) {
				st = new StringTokenizer(br.readLine());
				
				for (int k = 0; k < n; k++) {
					field[i][j][k] = Integer.parseInt(st.nextToken());
				}
			}
		}
		
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < m; j++) {
				for (int k = 0; k < n; k++) {
					if (field[i][j][k] == 1) { // 토마토가 익었을 때
						function(i, j, k);
					}
				}
			}
		}
		
		int count = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < m; j++) {
				for (int k = 0; k < n; k++) {
					
					// 전파가 끝나고도 익지 않은 토마토가 있을 때
					if (field[i][j][k] == 0) {
						count = -1;
						break;
					} else {
						count = Math.max(count, field[i][j][k] - 1);
					}
				}
				
				if (count == -1) {
					break;
				}
			}
			
			if (count == -1) {
				break;
			}
		}
		
		bw.write(Integer.toString(count));
		bw.flush();
		bw.close();
		br.close();
	}
	
	// 토마토가 전파를 하는 함수.
	private static void function(int hi, int y, int x) {
		Queue<Integer> hq = new LinkedList<>();
		Queue<Integer> yq = new LinkedList<>();
		Queue<Integer> xq = new LinkedList<>();
		hq.add(hi);
		yq.add(y);
		xq.add(x);
		
		int nowh, nowy, nowx, nexth, nexty, nextx;
		while (!hq.isEmpty()) {
			nowh = hq.poll();
			nowy = yq.poll();
			nowx = xq.poll();
			
			// 함수를 호출한 위치에서 총 6방향을 확인합니다.
			for (int i = 0; i < 6; i++) {
				nexth = nowh + dh[i];
				nexty = nowy + dy[i];
				nextx = nowx + dx[i];
				
				// 익지 않은 토마토일 때
				if (check(nexth, nexty, nextx) && field[nexth][nexty][nextx] == 0) {
					field[nexth][nexty][nextx] = field[nowh][nowy][nowx] + 1;
					hq.add(nexth);
					yq.add(nexty);
					xq.add(nextx);
					
					// 토마토가 익었지만 더 빨리 익을 수 있을 때
				} else if (check(nexth, nexty, nextx) && field[nexth][nexty][nextx] > field[nowh][nowy][nowx] + 1) {
					field[nexth][nexty][nextx] = field[nowh][nowy][nowx] + 1;
					hq.add(nexth);
					yq.add(nexty);
					xq.add(nextx);
				}
			}
		}
	}
	
	// 참조하는 위치가 밭 안에 있는지 확인하는 함수.
	private static boolean check(int hi, int y, int x) {
		return hi >= 0 && y >= 0 && x >= 0 && hi < h && y < m && x < n;
	}
}