[BAEKJOON] 7569번 토마토

이전에 토마토 문제를 다룬적이 있는데 아래 글 먼저 보고 오시면 좋을 것 같습니다.

오늘 문제는 이전 문제보다 조금 더 심화된 문제입니다.

2022.03.05 - [CODING/BAEKJOON] - [BEAKJOON] 7576번 토마토

[BEAKJOON] 7576번 토마토

---

 

0은 익혀야 할 토마토, 1은 익은 토마토, -1은 토마토가 없어서 방문하지 않아도 된다.

이번 문제는 토마토 상자가 n단으로 쌓아올려져 있고, 내 주변 상하좌우 방향 뿐만 아니라 현재 위치에서 쌓여있는 아래, 위 상자의 위치까지의 토마토를 고려해야 한다.

따라서 방향 배열 dx, dy를 상하좌우, 상자의 위 아래로 총 6가지로 생성한다.

N의 크기에 따라 위, 아래 상자로 나아가는 범위가 가변적이기 때문에 N을 입력 받은 후 아래와 같이 방향 배열을 초기화해준다.

순서대로 하, 상, 우, 좌, 아랫층, 윗층으로의 변화를 의미한다.

dx = new int[]{1, -1, 0, 0, -N, N};
dy = new int[]{0,  0, 1, -1,  0, 0};

 

 

만약 위의 그림과 같이 가로 M=5, 세로 N=3, 높이 H=3층의 토마토 상자가 있다고 할 때 위, 아래 상자 위치까지 고려해보자.

이차원배열 arr은 M * (N*H) 크기를 갖고, N의 배수씩 나누어 층을 구분할 수 있다.

 

현재 위치가 arr[4][2]라고 할 때 (x=4, y=2, arr[x][y]라 가정) 아래 상자는 arr[x-N], 위의 상자는 arr[x+N]위치가 된다.

 

상하좌우를 탐색할 때 고려해야할 범위가 있다. 기존 상하좌우 탐색은 현재 위치에서 위, 아래 상자로 넘어가면 안 되기 때문에 같은 층에서의 탐색만 허용한다. 즉 x의 범위를 조정해야 한다.

만약 현재 x위치가 4라면 2층을 의미하고, x의 범위는 아래와 같이 3~5로 제한해야 한다.

1층은 x>=0 && x<3   

2층은 x>=3 && x<6

3층은 x>=6 && x<9

위의 범위는 (현재 x 위치 / N ) * N로 구한다.

만약 내 x 위치가 4라면? (현재 x 위치 / N ) * N부터  (현재 x 위치 / N ) * N + N 까지

( 4 / 3 ) * 3으로 3이 나올 것이고, 범위는 최소 3부터 N을 더한 6까지일 것이다.

해당 범위를 벗어나지 않는 선에서 현재 위치에서의 기존 네 방향 탐색으로 상하좌우 범위에 맞추어 탐색하면 된다.

 

위, 아래 상자로 나아갈 때의 범위는 따로 지정하여 전체 배열 크기를 넘지 않는 범위로 제한한다.

 

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

public class Main {
	static int N, M, H;
	static int[] dx;
	static int[] dy;
	static String arr[][];
	static Queue<Point> queue = new LinkedList<>();
	static int cnt = 0, days = 0;
	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());
		arr = new String[N*H][M];
		dx = new int[]{1,-1,0,0, -N,N};
		dy = new int[]{0,0,1,-1,0,0};
		for(int i=0; i<N*H; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				String new_one = st.nextToken();
				arr[i][j] = new_one;
				if(new_one.equals("1")) {
					queue.add(new Point(i,j));	// 익은 토마도 큐에 넣기
				}else if(new_one.equals("0")) // 익혀야 하는 토마토 개수
					cnt++;
			}			
		}
		bfs();
		System.out.println((cnt==0)? days:-1);
	}
	
	static void bfs() {
		while(cnt>0 && !queue.isEmpty()) {
			// 하루에 익힐 수 있는 토마토 모두 큐에 넣기!
			for(int s = queue.size(); s>0; s--) {
				Point current = queue.poll();
				
				int current_x = current.x;
				int current_y = current.y;
				// 내 위치에서 주변 상하좌우
				for(int i=0; i<4; i++) {
					int new_x = current_x+dx[i];
					int new_y = current_y+dy[i];
					int range = (current_x/N)*N;
					if(new_x>=range && new_x<range+N && new_y>=0 && new_y<M && arr[new_x][new_y].equals("0")) {
						queue.add(new Point(new_x, new_y));
						arr[new_x][new_y] = "1";
						cnt--;	// 익힌 토마토는 총 개수에서 빼주기
					}
				}
                // 내 위치에서 상자 단위로 위 아래
				for(int i=4; i<6; i++) {
					int new_x = current_x+dx[i];
					int new_y = current_y+dy[i];
					int range = (current_x/N)*N;
					if(new_x>=0 && new_x<N*H && new_y>=0 && new_y<M && arr[new_x][new_y].equals("0")) {
						queue.add(new Point(new_x, new_y));
						arr[new_x][new_y] = "1";
						cnt--;	// 익힌 토마토는 총 개수에서 빼주기
					}
				}
			}
			days++; // 하루에 익힐 수 있는 토마토 모두 익혔어!
		}
	}

	static class Point{
		int x,y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

[출처]

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

7569번: 토마토