![[백준,BOJ 7569] 토마토2(JAVA 구현,추가풀이)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FywTc8%2FbtqzLjybIHU%2F4buNVbBxev9Ku3tGfdHfj1%2Fimg.png)
반응형
-내 생각
이 문제는 백준 7576 토마토 문제와 유사한 문제로 이번 문제에서는 단순히 토마토 상자가 하나가 있는 것이 아니라 토마토 상자가 여러 개 있을 경우에 대해서 물어보는 다차원 배열을 응용한 문제였다. 알고리즘 공부를 시작하고 다차원 배열을 사용하는 문제는 처음인 거 같은데 그래서 그런지 기존에 알고 있던 면, 행, 열 개념이 명확하지 않아서 조금 찾아본 후 구현했다. 자바에서 3차원 배열의 경우 int arr [][][] = new int [면], [행], [열]로 객체를 만들면 되며, 각 부분의 길이도 헷갈렸는데 출력으로 확인해본 바로 arr.length는 면의 길이(즉, 면의 개수) arr [면]. length가 행의 길이, arr [면][행]. length가 열의 길이가 된다. 뿐만 아니라 이번 문제에서는 한 토마토를 기준으로 사방을 살피는 것이 아닌, 육방 즉 상하도 포함되어야 하기 때문에 이전의 토마토 문제에서 별도의 2가지 조건만 추가하면 될 것 같다고 생각했다.
-해법
이전 토마토 문제와 유사하므로 새롭게 추가된 부분만 코드를 통해 확인해 보자.
import java.util.*;
class xy{ //xy좌표 저장 클래스
int x;
int y;
int z; // 면의 위치를 저장 할 변수를 하나 추가해준다.
public xy(int z,int x,int y) {
this.x= x;
this.y =y;
this.z = z;
}
}
public class Main {
static int node[][][]; // 높이를 고려하므로 3차원으로 선언한다.
static int check[][][];
static int cnt=1;
static int n,m,h;
public static void bfs(Queue<xy> q) { //BFS메소드
while(!q.isEmpty()) { // 이제 큐가 공백이 될 때 까지 반복한다.
int x = q.peek().x; // 큐에 저장되어 있는 객체에서 x,y좌표를 저장
int y = q.peek().y;
int z = q.peek().z; // z좌표도 고려해준다.
q.poll(); // 큐에서 peek후 저장한 것이기 때문에 별도이 poll()수행으로 해당 객체 소멸
if(y<node[z][x].length-1&& check[z][x][y+1]==0) { //열의 길이 조건 주의
check[z][x][y+1]=check[z][x][y]+1; // 현재 점이 가지고 있는 경로값을 인접한 점의 방문배열에 저장
q.offer(new xy(z,x,y+1)); // 인접한 점을 큐에 넣어준다.
//아래는 모두 이와 동일
}
if(x<node[z].length-1&&check[z][x+1][y]==0) { // 행의 길이 조건 주의
check[z][x+1][y]=check[z][x][y]+1;
q.offer(new xy(z,x+1,y));
} if(x>0&& check[z][x-1][y]==0) {
check[z][x-1][y]=check[z][x][y]+1;
q.offer(new xy(z,x-1,y));
}
if(y>0&& check[z][x][y-1]==0) {
check[z][x][y-1]=check[z][x][y]+1;
q.offer(new xy(z,x,y-1));
}
//아래 두 조건이 새롭게 추가된 2가지 조건 상, 하를 고려하는 조건문이다
//위의 조건문들과 다를바 없다.
if(z<node.length-1&& check[z+1][x][y]==0) {
check[z+1][x][y]=check[z][x][y]+1;
q.offer(new xy(z+1,x,y));
}
if(z>0&& check[z-1][x][y]==0) {
check[z-1][x][y]=check[z][x][y]+1;
q.offer(new xy(z-1,x,y));
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Queue<xy> queue = new LinkedList<>(); // 큐
m = sc.nextInt(); // 가로 , node[i][j].length
n = sc.nextInt(); // 세로 , node[i].length
h = sc.nextInt(); // 높이 , node.length
node = new int [h][n][m];
check = new int[h][n][m];
for(int k=0;k<h;k++) {
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
node[k][i][j] = sc.nextInt();
}
}
}
//이하 코드는 이전 토마토 문제와 동일하다 반복문1개씩만 추가해주면 된다.
for(int k=0;k<h;k++) {
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(node[k][i][j]==1 && check[k][i][j]==0) {
queue.add(new xy(k,i,j));
check[k][i][j] =1;
}
if(node[k][i][j]== -1)
check[k][i][j]=-1;
}
}
}
bfs(queue);
int max = Integer.MIN_VALUE;
for(int k=0;k<h;k++) {
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(check[k][i][j]==0) {
System.out.println("-1");
return;
}
if(check[k][i][j]>max) {
max = check[k][i][j];
}
}
}
}
System.out.println(max -1);
}
}
이전 토마토 문제와 사실상 같은 문제로 2차원으로 표현한 맵을 3차원으로 고려해 표현해 준 뒤 연산 부분을 3차원에 맞게 바꾸어 주면 된다. 바꾸는 과정이 좀 복잡하긴 했다.
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Dot{
int x;
int y;
int z;
public Dot(int x, int y, int z) {
super();
this.x = x;
this.y = y;
this.z = z;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public int getZ() {
return z;
}
public void setZ(int z) {
this.z = z;
}
}
class Main {
static Queue<Dot> q = new LinkedList<>();
// 탐색하고자 하는 방향을 제외하곤 0,0을 연산해주어 자리를 유지해준다.
static int dx[] = {0,0,0,0,1,-1}; // 면 탐색
static int dy[] = {1,-1,0,0,0,0}; // 행 탐색
static int dz[] = {0,0,1,-1,0,0}; // 열 탐색
// BFS 메소드
static void bfs(int[][][] a, int[][][] check) {
while(!q.isEmpty()) {
Dot d_p = q.poll();
int x = d_p.getX();// 면
int y = d_p.getY();// 행
int z = d_p.getZ();// 열
for(int i=0;i<6;i++) {
int nx = x + dx[i]; // 면
int ny = y + dy[i]; // 행
int nz = z + dz[i]; // 열
if(nx < 0 || nx>=a.length || ny>=a[nx].length || ny<0 || nz>=a[nx][ny].length || nz < 0 ) continue;
if(a[nx][ny][nz] == -1) continue;
if( check[nx][ny][nz] == Integer.MAX_VALUE ){
check[nx][ny][nz] = Math.min(check[x][y][z]+1,check[nx][ny][nz]);
q.offer(new Dot(nx,ny,nz));
}
}
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int h = in.nextInt();
int max = 0;
int map[][][] = new int[h][m][n];
int check[][][] = new int[h][m][n];
// 맵 입력
for(int i =0;i<map.length;i++) {
for(int j=0;j<map[i].length;j++) {
for(int k=0;k<map[i][j].length;k++) {
map[i][j][k] = in.nextInt();
}
}
}
// 최소 일 수를 파악하기 위해 체크 배열 초기화
for(int i =0;i<map.length;i++) {
for(int j=0;j<map[i].length;j++) {
Arrays.fill(check[i][j], Integer.MAX_VALUE);
}
}
Dot d;
// 익은 토마토이면서 방문하지 않은 좌표를 큐에 삽입
for(int i =0;i<map.length;i++) {
for(int j=0;j<map[i].length;j++) {
for(int k=0;k<map[i][j].length;k++) {
if(map[i][j][k] == 1 && check[i][j][k] == Integer.MAX_VALUE) {
d = new Dot(i,j,k);
q.offer(d);
check[i][j][k] = 1;
}else if (map[i][j][k] == -1)
check[i][j][k] = -1;
}
}
}
// BFS 수행
bfs(map,check);
// 최댓값이 최소일 수 가 된다.
for(int i =0;i<check.length;i++) {
for(int j=0;j<check[i].length;j++) {
for(int k=0;k<check[i][j].length;k++) {
if(max<check[i][j][k]) max = check[i][j][k];
}
}
}
if(max == 1) System.out.println(0);
else if(max == Integer.MAX_VALUE) System.out.println(-1);
else System.out.println(max - 1);
}
}반응형