알고리즘
[JAVA] 백준 7569번 - 토마토
ji_iin
2021. 7. 25. 15:33
문제
[ 문제 조건 ]
- 입력
- 1 = 익은 토마토
- 0 = 익지않은 토마토
- -1 = 토마토 없음
- 출력
- 0 = 저장될 때 모든 토마토 익음
- 1 = 모든 토마토 익지 못함
- n = 모두 익을 때 까지 최소 며칠이 걸리는지
- 보관 후 하루가 지나면 익은 토마토와 인접한 건 익음
[ 해결순서 ]
- 여태까지 풀던 문제는 상하좌우만 비교해서 해결하면 됐으나, 위 아래도 비교해서 6가지 경우를 비교해야한다.
- 3차원 배열로 가로,세로,높이의 값을 입력받고 너비우선탐색의 대상은 익은 값만 이므로 입력받을 때, 토마토가 익은 것들만 큐에 넣는다.
- 큐에 넣은 것들을 하나씩 꺼내며 너비우선탐색 한다.
- 기존 유사한 BFS 문제의 조건 비교에서 (가로, 세로 비교했던 것) 추가로 높이만 비교하고
- 토마토가 익었으면 (값이 0) 그 값을 큐에 넣어주고 기존 값 +1 값을 너비우선탐색한 배열에 넣는다.
- 이제 박스의 모든 값들을 꺼내면서 출력 조건에 맞게 출력한다. (자세한 건 주석확인)
✏️한줄평
문제 자체의 해결은 조금만 생각하면 이해가 됐는데, 처음 입력받을 때 M,N으로 변수 설정을 해놓고 뒤에 가서 코드를 작성하다보니 어떤 것이 X이고 Y인지 헷갈려 반대로 넣는 바람에 자꾸 인덱스 범위 벗어났다는 에러가 떴다. 이거 때문에 한시간 잡아먹은,,, 휴우,, 그래도 얻은게 많은 문제였다. 너비우선탐색 문제를 좀 더 자세히 알아간 기분이다.
코드
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package July_4; | |
| import java.io.BufferedReader; | |
| import java.io.IOException; | |
| import java.io.InputStreamReader; | |
| import java.util.LinkedList; | |
| import java.util.Queue; | |
| import java.util.StringTokenizer; | |
| class Tomato{ //클래스를 생성 | |
| int h,y,x; | |
| public Tomato(int h, int y, int x) { | |
| this.h = h; | |
| this.y = y; | |
| this.x = x; | |
| } | |
| } | |
| public class Main7569 { | |
| static int X,Y,H; | |
| static int[][][] boxes; | |
| static Queue<Tomato> q = new LinkedList<>(); | |
| static int[] dx = {-1, 0, 1, 0, 0, 0}; | |
| static int[] dy = {0, 1, 0, -1, 0, 0}; | |
| static int[] dh = {0, 0, 0, 0, 1, -1}; | |
| public static void main(String[] args) throws IOException { | |
| BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); | |
| StringTokenizer st = new StringTokenizer(br.readLine()); | |
| X = Integer.parseInt(st.nextToken()); //가로 | |
| Y = Integer.parseInt(st.nextToken()); //세로 | |
| H = Integer.parseInt(st.nextToken()); //높이 | |
| boxes = new int[H][Y][X]; | |
| //입력 | |
| for(int k=0; k < H; k++){ //높이 | |
| for(int i=0 ; i <Y ; i++){ //세로 | |
| st = new StringTokenizer(br.readLine()); | |
| for(int j=0 ; j <X ; j++){ //가로 | |
| boxes[k][i][j] = Integer.parseInt(st.nextToken()); | |
| if(boxes[k][i][j]==1) q.add(new Tomato(k,i,j)); //익은 토마토만 큐에 넣어 BFS | |
| } | |
| } | |
| } | |
| bfs(); | |
| } | |
| private static void bfs(){ | |
| while(!q.isEmpty()) { | |
| Tomato now = q.poll(); | |
| //M = 5, N = 3, H = 2 | |
| for (int i = 0; i < 6; i++) { | |
| int nextX = now.x + dx[i]; | |
| int nextY = now.y + dy[i]; | |
| int nextH = now.h + dh[i]; | |
| if (nextX < X && nextY <Y && nextH < H && nextX >=0 && nextY >=0 && nextH >=0 ) { //조건에 부합하고 | |
| if (boxes[nextH][nextY][nextX] == 0) { //토마토가 익었다면 | |
| q.add(new Tomato(nextH, nextY, nextX)); //조건에 맞는 토마토를 큐에 넣음 | |
| boxes[nextH][nextY][nextX] = boxes[now.h][now.y][now.x] + 1; //하나씩 늘려 며칠인지 확인 | |
| //즉 bfs 한번 돌릴때마다 하루가 지나감 | |
| // bfs를 확인하기 위해 프린트 해봄 | |
| // for(int t=0;t<H;t++){ | |
| // for(int j=0;j<Y;j++){ | |
| // for(int k=0;k<X;k++){ | |
| // System.out.print(boxes[t][j][k]); | |
| // } | |
| // System.out.println(); | |
| // } | |
| // } | |
| // System.out.println("---------"); | |
| } | |
| } | |
| } | |
| } | |
| int result = 0; | |
| for(int k=0; k<H; k++){ | |
| for(int i=0; i<Y; i++){ | |
| for(int j=0; j<X; j++){ | |
| if(boxes[k][i][j] == 0) {//0이 있다는 건 모든 토마토가 익어있지 않음 즉, 최소 1개 익지 않은 토마토가 잇음 | |
| System.out.println(-1); | |
| return; | |
| } | |
| result = Math.max(result,boxes[k][i][j]); | |
| } | |
| } | |
| } | |
| if(result == 1) System.out.println(0); //모두 확인해봤는데도 결과값이 1이라면 입력부터 모두 익었다는 뜻 | |
| else System.out.println(result-1); //며칠이 걸렸다면 결과 확인 | |
| } | |
| } |