[Java] 백준 - 7576번: 토마토

7월 7일(금) - 그래프와 순회 (7576번)

7576번: 토마토

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

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

import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int[][] tomato = new int[N][M];
        int cnt = 0;
        int days = 0;
        Queue<int[]> que = new LinkedList<>();

        for(int n=0; n<N; n++)
        {
            st = new StringTokenizer(br.readLine());
            for(int m=0; m<M; m++) {
                int num = Integer.parseInt(st.nextToken());
                tomato[n][m] = num;
                if (tomato[n][m] == 1)
                {
                    que.add(new int[] {n, m});
                }
                else if(tomato[n][m] == 0)
                {
                    cnt++;
                }
            }
        }

        while(cnt > 0 && !que.isEmpty())
        {
            for(int s = que.size(); s>0; s--)
            {
                int[] cur = que.poll();

                for(int k=0; k<4; k++)
                {
                    int next_y = cur[0] + dy[k];
                    int next_x = cur[1] + dx[k];

                    if(next_x<0 || next_y<0 || next_x>=M || next_y>=N || tomato[next_y][next_x] != 0)
                    {
                        continue;
                    }
                    cnt--;
                    tomato[next_y][next_x] = 1;
                    que.add(new int[] {next_y, next_x});
                }
            }
            days++;
        }
        System.out.println(cnt == 0 ? days : -1);
    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

풀이출처 -> https://girawhale.tistory.com/12