7576번 : 토마토

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

7576번: 토마토

 

 

문제

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static int[][] g;
    static int m;
    static int n;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};
    static Queue<int []> q = new LinkedList();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        g = new int[n][m];
        for(int i=0;i<n;i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0;j<m;j++) {
                g[i][j] = Integer.parseInt(st.nextToken());
                if(g[i][j] == 1) {
                    q.add(new int[]{i, j});
                }
            }
        }

        bw.write(bfs() + ""); bw.flush();
    }

    public static int bfs() {

        while(!q.isEmpty()) {
            int[] node = q.poll();
            int i = node[0];
            int j = node[1];

            for(int k=0;k<4;k++) {
                int x = i + dx[k];
                int y = j + dy[k];
                if(x<0 || y<0 || x>=n || y>=m) continue;
                if(g[x][y]==0) {
                    g[x][y] = g[i][j] + 1; //익은 날짜 저장
                    q.add(new int[]{x, y});
                }
            }
        }

        int result = -1;
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(g[i][j] == 0) return -1; //토마토가 모두 익지 못 하는 상황
                if(g[i][j]>result) result = g[i][j]; //촤대 날짜 구하기
            }
        }
        //익은 날짜 - 1 해줘야함
        return result-1;
    }
}

 

 

해결방법

문제를 잘못 이해해서 "익은 토마토 중 어떤 토마토부터 익어야 최소 일수를 구할 수 있는가 그때의 최소 일수를 구하라"로 알고 코드를 구현하였는데 생각해보니 이런 문제가 아니었다. 익은 토마토들은 하루가 지날 때마다 같이 익기 때문이다.

그래서 어떻게 풀지 다시 생각하였는데 도저히 생각이 안 났다. 입력받은 토마토 중 익은 토마토가 2개 이상일 때 이를 어떻게 같이 bfs로 처리할지 감이 안 왔기 때문이다. 결론은 다른 사람의 풀이를 참고하여 풀었다. 참고

 

 이 분은 입력받은 토마토 중 익은 토마토들을 큐에 모두 넣어서 bfs를 진행하였다. 이러면 익은 토마토가 여러 개여도 같이 익어갈 수 있다. 어떻게 이런 생각을 하였는지 존경스러웠다. 익은 날짜는 해당 토마토의 위치에 이전 토마토의 값 + 1을 하여 구현하셨다. 이후 최대 날짜만 구해 -1 하면 해결된다.

-1 하는 이유는 조금만 생각해보면 바로 이해될 것이다.

 

입력받은 토마토 칸

0 0 0 0 0 0                          1 -1 0 0 0 0  
0 0 0 0 0 0                          0 -1 0 0 0 0
0 0 0 0 0 0                          0 0 0 0 -1 0
0 0 0 0 0 1                          0 0 0 0 -1 1

bfs 진행 후 토마토 칸
9 8 7 6 5 4                          1 -1 7 6 5 4 
8 7 6 5 4 3                          2 -1 6 5 4 3 
7 6 5 4 3 2                          3 4 5 6 -1 2 
6 5 4 3 2 1                          4 5 6 7 -1 1 

 

출력

8                                         6

 

 

솔직히 이번 문제는 제대로 이해했으면 시도도 안 해봤을 문제였을 것 같다. 이 점에선 잘못 이해해서 좋은 부분(?)도 있는 것 같다.