Q.7576 자바: 토마토(G5)

문제 : https://www.acmicpc.net/problem/7576

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

그래프와 깊이 우선 탐색(DFS), 넓이 우선 탐색(BFS)는 사실 최대한 미루고 싶었는데,

이제는 해야될 떄가 된 것 같아 풀어보았다.

 

최대한 미룬 이유는 역시 생소한 개념이고 감을 잡기도 어려워서였다.

그래서 처음에는 그냥 답 맞추는 것을 목표로 풀어봤다.

---

이 문제는 결국 모든 토마토가 잘 익는데 얼마나 걸리는지를 계산하는 문제이므로

 

잘 익지 않은 토마토의 수(입력값 0)를 가져온 뒤

잘 익은 토마토(입력값 1) 근처 토마토는 다음날 잘 익은 토마토가 되므로

다음날 익을 예정(1이 될 예정)인 토마토를 2로 변경했다.

이 때 값이 -1, 1인곳은 변경하면 안되고, 값이 0인 토마토만 2로 변경하게 코드를 작성했다.

import java.io.BufferedReader;
        import java.io.IOException;
        import java.io.InputStreamReader;
        import java.util.*;


public class Main {

    private static BufferedReader br;
    private static StringBuffer sb;

    public static void main(String args[]) throws IOException {

        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuffer();

        String[] input = br.readLine().split(" ");
        int x = Integer.parseInt(input[0]);
        int y = Integer.parseInt(input[1]);

        int zeroCount = 0;
        int[][] tomato = new int[y][x];
        for(int i=0; i<y; i++){
            input = br.readLine().split(" ");
            for(int j=0; j<x; j++){
                int tmp = Integer.parseInt(input[j]);
                if(tmp == 0){
                    zeroCount++;
                }
                tomato[i][j] = tmp;
            }
        }

        int dayCount = 0;
        while (zeroCount > 0){
            for(int i=0; i<y; i++){
                for(int j=0; j<x; j++){
                    if(tomato[i][j] == 1){
                        if(i > 0){
                            if(tomato[i-1][j] == 0){
                                tomato[i-1][j] = 2;
                            }
                        }
                        if(i < y-1){
                            if(tomato[i+1][j] == 0){
                                tomato[i+1][j] = 2;
                            }
                        }
                        if(j > 0){
                            if(tomato[i][j-1] == 0){
                                tomato[i][j-1] = 2;
                            }
                        }
                        if(j < x-1){
                            if(tomato[i][j+1] == 0){
                                tomato[i][j+1] = 2;
                            }
                        }
                    }
                }
            }
            boolean isChanged = false;
            for(int i=0; i<y; i++) {
                for (int j = 0; j < x; j++) {
                    if(tomato[i][j] == 2){
                        tomato[i][j]--;
                        zeroCount--;
                        isChanged = true;
                    }
                }
            }

            if(!isChanged){
                dayCount = -1;
                break;
            }
            dayCount++;
        }

        System.out.println(dayCount);
    }

}

결과는 시간초과였다.

 

사실 풀면서도 효율적이지는 못한 코드라고 생각했고,

나름 고민을 해봤지만 이 코드에서 시간을 어디서 줄여야 할지 감이 안잡혀서 다른 사람들의 코드를 참고했다.

 

다른 사람들의 코드를 보니 내 코드와 거의 100% 달랐다. 다른 사람들의 경우

1) 토마토 좌표(x,y)를 저장하는 클래스를 하나 만듬

2) 토마토 근처(상하좌우)를 탐색하기 위해 dx, dy를 만들어 4번 반복해 탐색

3) 익은 토마토 Queue를 만들어 Queue에 값이 존재할 때 까지 토마토 농장 전체를 반복문을 이용해 탐색

   (설명이 길어져서 탐색이라고 작성했지만 실제로 정답을 위해 필요한 복잡한 로직이 들어가 있다.)

4) 이후 3번 로직을 이용해 나온 값을 이용해 정답 제출

정도 인것 같다.

 

개인적으로 2번 내용은 꼭 필요하지만, 나머지 방식들 모두 따라하면 나에게 아무런 도움도 안될 것 같아

2번 내용과 Queue를 사용한다는 점을 제외하고는 내가 처음 했던 방식으로 풀었다.

 

내가 작성한 코드의 로직을 설명하자면

1) 입력값을 좌표에 저장하며 익지 않은 토마토(0)의 전체 숫자를 센다.

2) 아래 반복문을 익지 않은 토마토의 수가 0이 되거나,

    아무 토마토도 변경되지 않을 때 까지 반복한다(=불가능)

    (isChanged = false일 경우 -1 출력, 실행 종료)

2) 익은 토마토(1)을 queue에 저장한다.

 

3) queue에 들어있는 익은 토마토(1)의 근처 익지 않은 토마토(0)를 nextDayQueue에 저장하고,

   변경될 토마토가 있음을 bool 타입의 isChanged 값을 통해 저장한다.

4) nextDayQueue를 queue에 복사하고, 하루를 증가시킨다. 3번으로 돌아간다.

import java.io.BufferedReader;
        import java.io.IOException;
        import java.io.InputStreamReader;
        import java.util.*;


public class Main {

    private static BufferedReader br;
    private static StringBuffer sb;

    public static void main(String args[]) throws IOException {

        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuffer();

        String[] input = br.readLine().split(" ");
        int x = Integer.parseInt(input[0]);
        int y = Integer.parseInt(input[1]);

        int zeroCount = 0;
        int[][] tomato = new int[y][x];
        Queue<int[]> queue = new LinkedList<>();
        for(int i=0; i<y; i++){
            input = br.readLine().split(" ");
            for(int j=0; j<x; j++){
                int tmp = Integer.parseInt(input[j]);
                if(tmp == 0){
                    zeroCount++;
                }else if(tmp == 1){
                    queue.add(new int[]{i, j});
                }
                tomato[i][j] = tmp;
            }
        }

        int dayCount = 0;
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};

        while (zeroCount > 0){
            Queue<int[]> nextDayQueue = new LinkedList<>();
            boolean isChanged = false;
            while (!queue.isEmpty()){
                int[] freshTomato = queue.poll();
                int curY = freshTomato[0];
                int curX = freshTomato[1];

                for(int i=0; i<4; i++){
                    int tmpY = curY + dy[i];
                    int tmpX = curX + dx[i];

                    if(tmpX < 0 || tmpY < 0 | tmpX == x || tmpY == y) continue;

                    if(tomato[tmpY][tmpX] == 0){
                        tomato[tmpY][tmpX]++;
                        zeroCount--;
                        isChanged = true;
                        nextDayQueue.add(new int[]{tmpY, tmpX});
                    }
                }
            }
            if(!isChanged){
                dayCount = -1;
                break;
            }
            queue.addAll(nextDayQueue);
            dayCount++;
        }

        System.out.println(dayCount);
    }

}

아마 더 효율적인 코드는 다른 사람들이 블로그에 작성해 놓은 글일 것 이다.

물론 그 코드들을 복사하면 당장은 효율적인 코드가 나오겠지만, 내가 성장하는 속도는 좀 더 늦을 것 같다.

사실 아직은 DFS를 어떻게 푸는지 명확히 감은 못잡은 상태이다.

그래도 계속 풀다보면 언젠간 쉬워지겠지..

 

코딩테스트 강의를 들으며 연습을 하다가 또 이 문제가 나왔는데

좀 더 괜찮은 코드가 나온 것 같아서 작성해본다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main{

    static int[][] tomatoArr;
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};
    static int dayCount = 0;

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());
        tomatoArr = new int[y][x];

        Queue<int[]> tomatoQueue = new LinkedList<>();
        int zeroCount = 0;
        for(int i=0; i<y; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<x; j++){
                tomatoArr[i][j] = Integer.parseInt(st.nextToken());
                if(tomatoArr[i][j] == 0){
                    zeroCount++;
                }else if(tomatoArr[i][j] == 1){
                    tomatoQueue.add(new int[] {i, j});
                }
            }
        }

        while (zeroCount > 0){
            Queue<int[]> nextDayQueue = new LinkedList<>();
            while (!tomatoQueue.isEmpty()){
                int[] tmpArr = tomatoQueue.poll();
                int tmpY = tmpArr[0];
                int tmpX = tmpArr[1];
                for(int i=0; i<4; i++){
                    int nextY = tmpY + dy[i];
                    int nextX = tmpX + dx[i];
                    if(nextX < 0 || nextY < 0 | nextX == x || nextY == y) continue;
                    if(tomatoArr[nextY][nextX] == 0){
                        nextDayQueue.add(new int[]{nextY, nextX});
                        tomatoArr[nextY][nextX] = 1;
                        zeroCount--;
                    }
                }
            }
            if(nextDayQueue.isEmpty()){
                dayCount = -1;
                break;
            }
            tomatoQueue = nextDayQueue;
            dayCount++;
        }
        System.out.println(dayCount);
    }
}

 

 

거의 동일한 문제인데 z축이 추가된 문제도 있다. 이 문제를 풀었다면 충분히 풀만해 보인다(바꿀 코드가 별로 없다!)

https://www.acmicpc.net/problem/7569