[백준/java] 7569번 : 토마토(3차원배열) BFS

7569번 : 토마토(3차원배열)

 

728x90

 

7569번: 토마토

 

7569번 : 토마토(3차원배열) BFS

 

※ 문제풀이

이번 문제는  2차원 배열로 푸는 토마토 문제(7576)와 방법은 똑같고 다만 3차원배열이어서 동서남북 + 위 아래까지 조회를 해주면 된다.

그러면 7576번 토마토와 비교해서 어떤 것이 추가되었는지 확인해보자.

 

먼저 변수 선언부

	static int[][][] map;
	static boolean[][][] visit;
	static int M, N, H;
	static int[][] dx, dy, dh;
	static class Node {
		int y, x, h, step;
		public Node(int h, int y, int x,int step) {
			this.y = y;
			this.x = x;
			this.h = h;
			this.step = step;
		}
	}

int형 3차원 배열 map, boolean형 3차원 배열 visit은 차원이 하나씩 추가되었다.

그리고 dx, dy 는 2차원 배열로, 그리고 dh 배열이 추가되었다.

 

반응형

 

기존 dy, dx는 1차원 배열로서 dy = {-1, 0, 1, 0}, dx= {0, 1, 0 , -1} 처럼

(-1, 0), (0 ,1), (1, 0), (0, -1) 순으로 (0, 0) 기준으로 북, 동, 남, 서 순으로 활용을 했었다. 

 

그러나 이번 문제에서는 dh, 층이 추가됨으로써 dy, dx, dh 모두 이차원 배열로 다뤄야 한다.

map = new int[H][N][M];
visit = new boolean[H][N][M];
dx = new int[H][6];
dy = new int[H][6];
dh = new int[H][6];
		
for (int i = 0; i < H; i++) {
	dx[i][0] = 1; dx[i][1] = 0; dx[i][2] = -1; dx[i][3] = 0; dx[i][4] = 0; dx[i][5] = 0;
	dy[i][0] = 0; dy[i][1] = 1; dy[i][2] = 0; dy[i][3] = -1; dy[i][4] = 0; dy[i][5] = 0;
	dh[i][0] = 0; dh[i][1] = 0; dh[i][2] = 0; dh[i][3] = 0; dh[i][4] = 1; dh[i][5] = -1;
}

현재 위치 (0, 0)으로 순회할 때, i가 0번째이면, 0번째 층의 상자에서 0번째 x는 1, y는 0, h는 0이므로, 우측으로 한번 이동하고, 층 이동이나, 위나 아래로 움직이는 것은 없다는 의미이다.

 

그리고 BFS로 순회할 큐와 경과일수를 체크할 날짜를 담을 변수가 필요하다

int day = 0;
Queue<Node> q = new LinkedList<Node>();

 

입력받는 값들 중에서 1, 즉 토마토가 있는 곳이면 위치를 큐에 저장해줘야한다.

for (int h = 0; h < H; h++) {
	for (int r = 0; r < N; r++) {
		st = new StringTokenizer(br.readLine(), " ");
		for (int c = 0; c < M; c++) {
			int tomato = stoi(st.nextToken());
			map[h][r][c] = tomato;
			if(tomato == 1) {
				q.add(new Node(h, r, c, 0));
			}
		}
	}
}

 

그리고 큐에서 하나씩 뽑으면서 현재 뽑은 위치에서 상, 하, 좌, 우, 위, 아래를 비교해가면서 박스 영역을 벗어나는지, 방문한 곳인지, 토마토가 있는지 없는지를 비교해가면서 확인해야한다.

만약에 익지 않은 토마토가 있는 곳이라면 익지 않은 토마토를 익은 토마토로 바꿔주고 다음 노드를 탐색하기 위해서 큐에 익은 토마토로 바꿔준 위치와 증가된 일자(step)을 넣어준다.

while(!q.isEmpty()) {
	Node cur = q.poll();
	visit[cur.h][cur.y][cur.x] = true;
		
	for (int dir = 0; dir < 6; dir++) {
		int nh = cur.h + dh[cur.h][dir];
		int ny = cur.y + dy[cur.h][dir];
		int nx = cur.x + dx[cur.h][dir];
		
		if(nh < 0 || nh >= H || ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
		if(visit[nh][ny][nx] || map[nh][ny][nx] == -1 || map[nh][ny][nx] == 1) continue;
		
		map[nh][ny][nx] = 1;
		int step = cur.step + 1;
		q.add(new Node(nh, ny, nx, step));
	}
			
	day = cur.step;
}

 

그리고 이제 출력인데, 토마토 중에 익지 않은 토마토가 있다면 -1을 출력, 그렇지 않으면 경과된 일을 출력한다.

for (int h = 0; h < H; h++) {
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			if(map[h][r][c] == 0) {
				System.out.println(-1);
				return;
			}
		}
	}
}
		
System.out.println(day);

 

 

다음은 종합적인 소스코드이다.

package bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Tomato2 {
	static int[][][] map;
	static boolean[][][] visit;
	static int M, N, H;
	static int[][] dx, dy, dh;
	static class Node {
		int y, x, h, step;
		public Node(int h, int y, int x,int step) {
			this.y = y;
			this.x = x;
			this.h = h;
			this.step = step;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		M = stoi(st.nextToken());
		N = stoi(st.nextToken());
		H = stoi(st.nextToken());
		
		int day = 0;
		
		Queue<Node> q = new LinkedList<Node>();
		
		map = new int[H][N][M];
		visit = new boolean[H][N][M];
		dx = new int[H][6];
		dy = new int[H][6];
		dh = new int[H][6];
		
		for (int i = 0; i < H; i++) {
			dx[i][0] = 1; dx[i][1] = 0; dx[i][2] = -1; dx[i][3] = 0; dx[i][4] = 0; dx[i][5] = 0;
			dy[i][0] = 0; dy[i][1] = 1; dy[i][2] = 0; dy[i][3] = -1; dy[i][4] = 0; dy[i][5] = 0;
			dh[i][0] = 0; dh[i][1] = 0; dh[i][2] = 0; dh[i][3] = 0; dh[i][4] = 1; dh[i][5] = -1;
		}
		
		for (int h = 0; h < H; h++) {
			for (int r = 0; r < N; r++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int c = 0; c < M; c++) {
					int tomato = stoi(st.nextToken());
					map[h][r][c] = tomato;
					if(tomato == 1) {
						q.add(new Node(h, r, c, 0));
					}
				}
			}
		}
		
		while(!q.isEmpty()) {
			Node cur = q.poll();
			visit[cur.h][cur.y][cur.x] = true;
			
			for (int dir = 0; dir < 6; dir++) {
				int nh = cur.h + dh[cur.h][dir];
				int ny = cur.y + dy[cur.h][dir];
				int nx = cur.x + dx[cur.h][dir];
				
				if(nh < 0 || nh >= H || ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
				if(visit[nh][ny][nx] || map[nh][ny][nx] == -1 || map[nh][ny][nx] == 1) continue;
				
				map[nh][ny][nx] = 1;
				int step = cur.step + 1;
				q.add(new Node(nh, ny, nx, step));
			}
			
			day = cur.step;
		}
		
		for (int h = 0; h < H; h++) {
			for (int r = 0; r < N; r++) {
				for (int c = 0; c < M; c++) {
					if(map[h][r][c] == 0) {
						System.out.println(-1);
						return;
					}
				}
			}
		}
		
		System.out.println(day);
	}
	
	public static int stoi(String str) {
		return Integer.parseInt(str);
	}
}