[BFS] 백준 7569번 토마토 - JAVA (3차원을 곁들인 토마토)

 

 

[BFS] 백준 7576번 토마토 - JAVA

 

 

어제 푼 2차원 토마토에 이어 3차원 토마토를 풀 것이다.

민성, 호진 오빠한테 일기 썼다며, 토마토 문제를 보여줬더니

민성오빠가 3차원 토마토냐 2차원 토마토냐라고 물어봐서 2차원이라 했더니

3차원 토마토 추천한다고 해서 풀어보았다.

 

3차원 토마토 박스

옆에 있던 영헌오빠도 강추했다.

본격 알고리즘 영재들이 추천하는 토마토 3차원 문제 LET'S GO

 

 

---

1. 문제 출처

---

 

 

7569번: 토마토

 

 

---

2. 설계

---

 

1) 익은 토마토 6방으로 안익은 토마토가 익는다.

2차원 토마토와 다른 점은 상하좌우 4방 탐색이 아닌 상하좌우 / 3차원 상하까지 6방향을 탐색한다는 것이다. 그렇기 때문에 익은 토마토들의 좌표를 큐에 넣고, 그 토마토들부터 6방 탐색을 시작해야겠다고 생각했다. 때문에 데이터를 입력받음과 동시에 익은 토마토(1)인 곳을 큐에 넣어줬다. 큐에 넣어주면서 이 공간의 토마토는 이미 익었다는 표시로 visited = true를 해주었다.

M = sc.nextInt();//가로
N = sc.nextInt();//세로
H = sc.nextInt();//높이
        
arr = new int[H][N][M];
visited = new boolean[H][N][M];
        
for(int i=0;i<H;i++) {
	for(int j=0;j<N;j++) {
		for(int k=0;k<M;k++) {
			arr[i][j][k] = sc.nextInt();
                    
			//익은 토마토 우선순위 큐에 넣기
			if(arr[i][j][k] == 1) {
				pq.add(new Tomato(i,j,k,0));
				visited[i][j][k] = true;
			}
		}
	}
}//for end

또 주의해야할 것은 3차원 배열 관리이다. 나는 처음에 [행][열][높이] 순으로 데이터를 입력받았는데, 데이터를 출력하다보니 [높이][행][열] 순으로 데이터를 입력받아 관리해야한다는 것을 깨달았다. 1번 높이의 행렬 데이터, 2번 높이의 행렬 데이터... 라고 생각하면 될 것같다.

 

 

2) 처음부터 다 익은 토마토의 케이스는 결과 0을 출력한다.

익을 시간이 필요없으니까 필요한 시간은 0인 것이다. 때문에 본격적인 알고리즘을 돌리기 전에 토마토가 없는 공간을 제외하고, 모두 익었는지 확인한다. 즉, visited가 모두 true인지 확인한다.

 

public static boolean growAll() {
	for(int i=0;i<H;i++) {
		for(int j=0;j<N;j++) {
			for(int k=0;k<M;k++) {
				//토마토가 빈곳이 아닌데, 익지 않았다면 false
				if(arr[i][j][k]!=-1&&visited[i][j][k] == false) {
					return false;
				}
			}
		}
	}//for end
	return true;//모두 익었다.
}

 

 

3) 토마토가 다 익은 상태가 아니라면, 익히러 가자!

여기서부터는 2차원 토마토와 똑같다. 미리 익은 토마토의 좌표를 넣어준 큐에서 하나씩 꺼내고, 그 좌표 기준으로 6방 탐색을 하면서 1) 경계 범위에 있는지 2) 이미 익은 토마토인지 (visited 체크) 3) 토마토가 없는 곳인지 확인해주고, 이 세 케이스에 모두 속하지 않는다면, 토마토를 익히고(visited=true), 큐에 넣는다. 해당 과정을 프림알고리즘을 사용하였다.

//prim algo
public static void grow() {
	//4방탐색 & 3차원 위 아래 탐색
	int[][] drc = {{0,-1,0},{0,1,0},{0,0,-1},{0,0,1},{-1,0,0},{1,0,0}};//상하좌우 / 3차원 위 아래

	while(!pq.isEmpty()) {
        	
		Tomato cur = pq.poll();
            
		if(result<cur.day) result=cur.day;
            
		for(int d=0;d<6;d++) {
			int nextI = cur.i+drc[d][0];
			int nextJ = cur.j+drc[d][1];
			int nextK = cur.k+drc[d][2];
                
			//범위탐색
			if(nextI<0 || nextI>=H || nextJ<0 || nextJ>=N || nextK<0 || nextK>=M) continue;
                
			if(arr[nextI][nextJ][nextK] == -1) continue;//벽이면 스킵
                
			if(visited[nextI][nextJ][nextK]) continue; //이미 익은 토마토면 스킵
                
			pq.add(new Tomato(nextI,nextJ,nextK,cur.day+1));
			visited[nextI][nextJ][nextK]=true;
		}
	}
}

이 과정을 큐에 익은 토마토가 다 떨어질 때까지 계속한다.

 

 

4) 모든 토마토가 다 익었는지 확인한다.

벽에 막혀서 6방탐색이 닿지 않아 익지 않는 토마토가 생길 수 있다. 때문에 2번 과정에서 진행했던 allGrow 함수를 재사용하여 토마토가 없는 곳 제외하고, 모든 토마토가 익었는지 확인한다. (visited = true인지 확인한다.)

public static boolean growAll() {
	for(int i=0;i<H;i++) {
		for(int j=0;j<N;j++) {
			for(int k=0;k<M;k++) {
				//토마토가 빈곳이 아닌데, 익지 않았다면 false
				if(arr[i][j][k]!=-1&&visited[i][j][k] == false) {
					return false;
				}
			}
		}
	}//for end
	return true;//모두 익었다.
}

 

 

---

3. 전체 코드

---

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    
    static Queue<Tomato> pq = new PriorityQueue<>();
    static boolean[][][] visited;
    static int M,N,H,result;
    static int[][][] arr;
    
    static class Tomato implements Comparable<Tomato>{
        int i;
        int j;
        int k;
        int day;//토마토가 얼마나 지나 익었는지
        public Tomato(int i, int j, int k, int day) {
            super();
            this.i = i;
            this.j = j;
            this.k = k;
            this.day = day;
        }
        
        @Override
        public int compareTo(Tomato o) {
            return this.day>o.day?1:-1;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        M = sc.nextInt();//가로
        N = sc.nextInt();//세로
        H = sc.nextInt();//높이
        
        arr = new int[H][N][M];
        visited = new boolean[H][N][M];
        
        for(int i=0;i<H;i++) {
            for(int j=0;j<N;j++) {
                for(int k=0;k<M;k++) {
                    arr[i][j][k] = sc.nextInt();
                    
                    //익은 토마토 우선순위 큐에 넣기
                    if(arr[i][j][k] == 1) {
                        pq.add(new Tomato(i,j,k,0));
                        visited[i][j][k] = true;
                    }
                }
            }
        }//for end
        
        //입력 받기 완료
        
        //만약 초장부터 토마토가 다 익어있었다면 0을 출력
        if(growAll()) {
            result=0;
        }else {
            //토마토가 다 안익었으면 익히는 작업 시작
            grow();
            
            //작업 후 안익은 토마토가 존재하면 -1
            if(!growAll()) {
                result = -1;
            }
        }
        
        //결과출력
        System.out.println(result);
    }
    
    //prim algo
    public static void grow() {
        //4방탐색 & 3차원 위 아래 탐색
        int[][] drc = {{0,-1,0},{0,1,0},{0,0,-1},{0,0,1},{-1,0,0},{1,0,0}};//상하좌우 / 3차원 위 아래

        while(!pq.isEmpty()) {
        	
            Tomato cur = pq.poll();
            
            if(result<cur.day) result=cur.day;
            
            for(int d=0;d<6;d++) {
                int nextI = cur.i+drc[d][0];
                int nextJ = cur.j+drc[d][1];
                int nextK = cur.k+drc[d][2];
                
                //범위탐색
                if(nextI<0 || nextI>=H || nextJ<0 || nextJ>=N || nextK<0 || nextK>=M) continue;
                
                if(arr[nextI][nextJ][nextK] == -1) continue;//벽이면 스킵
                
                if(visited[nextI][nextJ][nextK]) continue; //이미 익은 토마토면 스킵
                
                pq.add(new Tomato(nextI,nextJ,nextK,cur.day+1));
                visited[nextI][nextJ][nextK]=true;
            }
        }
    }
    
    public static boolean growAll() {

        for(int i=0;i<H;i++) {
            for(int j=0;j<N;j++) {
                for(int k=0;k<M;k++) {
                    //토마토가 빈곳이 아닌데, 익지 않았다면 false
                    if(arr[i][j][k]!=-1&&visited[i][j][k] == false) {
                        return false;
                    }
                }
            }
        }//for end
        
        return true;//모두 익었다.
    }
}

 

 

---

 

3차원 배열... 이제서야 이해하다니...

그래도 이제서야 이해한 게 어딘가