[백준, 자바, 7569번] 토마토

풀이

• 해당 문제는 3차원 배열 문제로, 파이썬 사용할 때 관련 문제를 풀어봤고
• 자바로는 처음이라 도키도키 했음
• 그래서 첫 풀이 과정은
  • 그냥 일반 bfs처럼 해결하면서,
  • 주위에 안 익은 토마토가 있는 좌표만 dq에 추가하고,
  • 이후에 dq를 탐색하면서 해당 좌표 주위에 있는
  • 안 익은 토마토를 익히게 하며 카운팅 후 결과를 도출하고자 했음
  • 그러나 시간초과.
  • 물론 처음 코드를 작성할 때도, 유사한 로직이 한 번 더 있고
  • 다 차원의 for문과 while문이 있으니 쉽지 않을 것 같다고 생각을 했지만,
  • 그래도 안 익은 토마토 주위에 있는 토마토만을 dq에 추가하니까 
  • 시간적으로 효율이 괜찮지 않을까? 하고 제출을 했지만 
  • 시간초과가 나서 고민을 하게 됨.
• 이후 두 번째 풀이 과정으로
  • 중복되는 코드 로직을 없애고,
  • 그냥 단순히 첫 데이터를 mtx에 추가할 때
  • 조건으로 1이면 dq에 좌표와 반복 체크를 위한 0을 추가, 0이면 카운팅 후
  • 이후 dq에서 하나 씩 조회하면서,
  • 범위 조사 후 해당 좌표가 안 익은 토마토라면 익히게 한 다음,
  • 해당 좌표를 dq에 다시 추가 후,
  • 안 익은 토마토 카운팅 한 것을 1개씩 차감
  • 이후 dq에 아무것도 남아 있지 않을 경우 while을 탈출하고
  • cnt가 0이 아닐 경우엔, 안 익은 토마토가 있다는 것으로
  • -1을 출력하고, 0일 경우 result를 출력하여 해결.

 

// 첫 풀이 방법(시간 초과)

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] MNH = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[][][] mtx = new int[MNH[2]][MNH[1]][MNH[0]];
        int[] nj = {-1,0,1,0};
        int[] nk = {0,1,0,-1};
        Deque<List<Integer>> dq = new ArrayDeque<>();
        StringTokenizer st;
        for (int i=0; i<MNH[2]; i++) {
            for (int j=0; j<MNH[1]; j++) {
                st = new StringTokenizer(br.readLine());
                for (int k=0; k<MNH[0]; k++) {
                    mtx[i][j][k] = Integer.parseInt(st.nextToken());
                }
            }
        }

        int result = 0;
        int cnt = 0;
        while (true) {
            // 안 익은 토마토 주위에 있는 익은 토마토 위치 추가, 안 익은 토마토 개수 체크
            for (int i=0; i<MNH[2]; i++) {
                for (int j=0; j<MNH[1]; j++) {
                    for (int k=0; k<MNH[0]; k++) {
                        if (mtx[i][j][k]==1) {
                            boolean state = false;
                            for (int x=0; x<4; x++) {
                                if ((0<=j+nj[x] && j+nj[x]<MNH[1]) && (0<=k+nk[x] && k+nk[x]<MNH[0]) && mtx[i][j+nj[x]][k+nk[x]]==0) {
                                    state = true;
                                    break;
                                }
                            }
                            if (0<=i-1 && mtx[i-1][j][k]==1) state = true;
                            else if (i+1<MNH[2] && mtx[i+1][j][k]==1) state = true;
                            if (state) dq.add(new ArrayList<>(Arrays.asList(i,j,k)));
                        }
                        else if (mtx[i][j][k]==0) cnt++;
                    }
                }
            }

            if (cnt==0 || dq.isEmpty()) break;
            // 이제 익은 토마토 주위에 있는, 익지 않은 토마토 익히기
            while (!dq.isEmpty()) {
                List<Integer> li = dq.pollFirst();
                for (int x=0; x<4; x++) {
                    if ((0<=li.get(1)+nj[x] && li.get(1)+nj[x]<MNH[1]) && (0<=li.get(2)+nk[x] && li.get(2)+nk[x]<MNH[0]) && mtx[li.get(0)][li.get(1)+nj[x]][li.get(2)+nk[x]]==0) {
                        mtx[li.get(0)][li.get(1)+nj[x]][li.get(2)+nk[x]] = 1;
                    }
                }
                if (0<=li.get(0)-1 && mtx[li.get(0)-1][li.get(1)][li.get(2)]==0) mtx[li.get(0)-1][li.get(1)][li.get(2)] = 1;
                if (li.get(0)+1<MNH[2] && mtx[li.get(0)+1][li.get(1)][li.get(2)]==0) mtx[li.get(0)+1][li.get(1)][li.get(2)] = 1;
            }
            result ++;
            cnt = 0;
        }

        System.out.println(cnt!=0?-1:result);
    }
}

// 두 번째 풀이 (성공)

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] MNH = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[][][] mtx = new int[MNH[2]][MNH[1]][MNH[0]];
        int[] nj = {-1,0,1,0};
        int[] nk = {0,1,0,-1};
        Deque<List<Integer>> dq = new ArrayDeque<>();
        StringTokenizer st;
        int cnt = 0;
        for (int i=0; i<MNH[2]; i++) {
            for (int j=0; j<MNH[1]; j++) {
                st = new StringTokenizer(br.readLine());
                for (int k=0; k<MNH[0]; k++) {
                    mtx[i][j][k] = Integer.parseInt(st.nextToken());
                    if (mtx[i][j][k]==1) dq.add(new ArrayList<>(Arrays.asList(i,j,k,0)));
                    else if (mtx[i][j][k]==0) cnt++;
                }
            }
        }

        int result = 0;

        while (true) {

            if (dq.isEmpty()) break;
            while (!dq.isEmpty()) {
                List<Integer> li = dq.pollFirst();
                if (li.get(3) > result) result = li.get(3);
                for (int x=0; x<4; x++) {
                    if ((0<=li.get(1)+nj[x] && li.get(1)+nj[x]<MNH[1]) && (0<=li.get(2)+nk[x] && li.get(2)+nk[x]<MNH[0]) && mtx[li.get(0)][li.get(1)+nj[x]][li.get(2)+nk[x]]==0) {
                        mtx[li.get(0)][li.get(1)+nj[x]][li.get(2)+nk[x]] = 1;
                        dq.add(new ArrayList<>(Arrays.asList(li.get(0), li.get(1)+nj[x], li.get(2)+nk[x], li.get(3)+1)));
                        cnt--;
                    }
                }
                if (0<=li.get(0)-1 && mtx[li.get(0)-1][li.get(1)][li.get(2)]==0) {
                    mtx[li.get(0)-1][li.get(1)][li.get(2)] = 1;
                    dq.add(new ArrayList<>(Arrays.asList(li.get(0)-1, li.get(1), li.get(2), li.get(3)+1)));
                    cnt--;
                }
                if (li.get(0)+1<MNH[2] && mtx[li.get(0)+1][li.get(1)][li.get(2)]==0) {
                    mtx[li.get(0) + 1][li.get(1)][li.get(2)] = 1;
                    dq.add(new ArrayList<>(Arrays.asList(li.get(0)+1, li.get(1), li.get(2), li.get(3)+1)));
                    cnt--;
                }
            }
        }

        System.out.println(cnt!=0?-1:result);
    }
}