[백준] 7569 문제 - 토마토(Java) 문제 해결 방법과 풀이코드

이 토마토 문제는 골드5 문제로 실버 단계에서 풀던 bfs 공식 으로 풀리지가 않았다.

기존 bfs의 공식이라 함은 for문을 돌아서 1을 찾은 다음 바로 큐에 담고 방문체크를 한 다음에 bfs를 돌리는 것인데 똑같이 이렇게 푸니 절대로 풀리지 않는 문제가 있었다.

 

기존 풀이 코드

for (int i = 0; i < mapZ; i++) {
    for (int j = 0; j < mapY; j++) {
       for (int k = 0; k < mapX; k++) {
          if (map[i][j][k] == 1 && !isVisited[i][j][k]) {
             isVisited[i][j][k] = true;
             bfs(i, j, k);
          }
       }
    }
}

 

직면한 문제와 해결 방법

만약 입력이 아래 처럼 주어졌을 때 밑에 1을 찾아 바로 bfs 돌면 인접해 있는 것들 모두 방문하게 돼서  인접한 토마토가 있음에도 불구하고 토마토 익은 일수가 2가 돼 버린다.

 

2 2 1                      익은 일수
0 0          -->         1 2 
1 1                          0 0

 

어떻게 해결할지 고민 하다가 문제 해결 방법을 보니 for문에서 bfs() 돌리기전에 1을 모두 큐에 담는 것이 해결 방법 이였다.

 

개선 코드

for (int i = 0; i < mapZ; i++) {
    for (int j = 0; j < mapY; j++) {
       for (int k = 0; k < mapX; k++) {
          if (map[i][j][k] == 1 && !isVisited[i][j][k]) {
             isVisited[i][j][k] = true;
             queue.add(new int[] {i, j, k});
          }
       }
    }
}

bfs();

 

위 처럼 1을 찾아 모두 큐에 담고 마지막에 bfs() 돌려 해결 하였다.

2 2 1                      익은 일수
0 0          -->         1 1 
1 1                          0 0

 

전체 풀이 코드

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

//https://www.acmicpc.net/problem/7569
public class 토마토_7569 {
    /**
     * 아이디어
     * 1. 3차 for문을 돌아서 1인걸 찾아서 bfs() 실행시킨다.
     * 2. 토마토 상자의 값이 0 인데 방문체크가 false면 -1을 리턴한다.
     * 3. 토마토 익은 날짜를 담는 배열을 하나 만들어서 정답을 출력한다.
     * 4. 큐를 돌아서 방문할때마다 큐의 x,y,z의 값 + 1 한 값을 tomatoRipeDay 에 담는다.
     * 5. tomatoRipeDay에서 가장 큰 값을 출력한다.
     *
     * 자료구조
     * - 토마토 상자 : int[z][y][x] map
     * - 토마토가 익은 날짜 : int[z][y][x] tomatoRipeDay
     * - 방문 체크 : boolean[z][y][x] isVisited
     * - 가로이동 : int[] = new int[]{0, 1, 0, -1, 0, 0}
     * - 세로이동 : int[] = new int[]{1, 0, -1, 0, 0, 0}
     * - 위아래이동 : int[] = new int[]{0, 0, 0, 0, 1, -1}
     */

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st = null;

    static int[][][] map = null;
    static int[][][] tomatoRipeDay = null;
    static boolean[][][] isVisited = null;
    static int mapZ, mapY, mapX;
    static Queue<int[]> queue = new LinkedList<>();

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

    private static void input() throws Exception {
       //가로x, 세로y, 상자높이 z입력
       st = new StringTokenizer(br.readLine());
       mapX = Integer.parseInt(st.nextToken());
       mapY = Integer.parseInt(st.nextToken());
       mapZ = Integer.parseInt(st.nextToken());

       map = new int[mapZ][mapY][mapX];
       tomatoRipeDay = new int[mapZ][mapY][mapX];
       isVisited = new boolean[mapZ][mapY][mapX];

       //z, y, x 3중 for문 한줄 마다 map에 인입
       for (int i = 0; i < mapZ; i++) {
          for (int j = 0; j < mapY; j++) {
             st = new StringTokenizer(br.readLine());
             for (int k = 0; k < mapX; k++) {
                map[i][j][k] = Integer.parseInt(st.nextToken());
             }
          }
       }
    }

    public static void main(String[] args) throws Exception {
       input();

       solve();

       print();
    }

    private static void print() {
       //토마토 상자의 값이 0 인데 방문체크가 false면 -1을 리턴한다.
       for (int i = 0; i < mapZ; i++) {
          for (int j = 0; j < mapY; j++) {
             for (int k = 0; k < mapX; k++) {
                if (map[i][j][k] == 0 && !isVisited[i][j][k]) {
                   System.out.println(-1);
                   return;
                }
             }
          }
       }

       int answer = 0;
       //tomatoRipeDay에서 가장 큰 값을 출력한다.
       for (int i = 0; i < mapZ; i++) {
          for (int j = 0; j < mapY; j++) {
             for (int k = 0; k < mapX; k++) {
                answer = Math.max(tomatoRipeDay[i][j][k], answer);
             }
          }
       }
       System.out.println(answer);
    }

    private static void solve() {
       for (int i = 0; i < mapZ; i++) {
          for (int j = 0; j < mapY; j++) {
             for (int k = 0; k < mapX; k++) {
                if (map[i][j][k] == 1 && !isVisited[i][j][k]) {
                   isVisited[i][j][k] = true;
                   queue.add(new int[] {i, j, k});
                }
             }
          }
       }

       bfs();
    }

    private static void bfs() {
       while (!queue.isEmpty()) {
          int[] curZYX = queue.poll();
          int curZ = curZYX[0];
          int curY = curZYX[1];
          int curX = curZYX[2];
          int curDay = tomatoRipeDay[curZ][curY][curX];

          for (int i = 0; i < dx.length; i++) {
             int qz = curZ + dz[i];
             int qy = curY + dy[i];
             int qx = curX + dx[i];

             if (qz >= 0 && qz < mapZ && qy >= 0 && qy < mapY && qx >= 0 && qx < mapX
                && map[qz][qy][qx] == 0 && !isVisited[qz][qy][qx]) {

                isVisited[qz][qy][qx] = true;
                tomatoRipeDay[qz][qy][qx] = curDay + 1;
                queue.add(new int[] {qz, qy, qx});
             }
          }
       }
    }
}