[백준 7576번 / Java] 토마토

[백준 7576번 / Java] 토마토 - BFS코딩테스트/백준2023. 7. 5. 06:00@mag1c

Table of Contents

728x90

문제 링크

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

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토

www.acmicpc.net

풀이

BFS를 이용한 단순한 풀이였지만, 정답을 맞춘 뒤 맘에 들지않는 부분을 수정하였다.

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 BaekJoon7576 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int[][] tomato = new int[N][M];
        Queue<int []> queue = new LinkedList<>();
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            for(int j = 0; j < M; j++) {
                int number = Integer.parseInt(st.nextToken());
                tomato[i][j] = number;

                if(number == 1) {
                    queue.add(new int[] {i, j});
                }
            }

        }

        int day = queue.isEmpty() ? -1 : 0;
        int[] tmp1 = new int[] {1, -1, 0, 0};
        int[] tmp2 = new int[] {0, 0, 1, -1};

        while(!queue.isEmpty()) {
            int size = queue.size();
            int cnt = 0;

            for (int i = 0; i < size; i++) {
                int[] tmp = queue.poll();
                int y = tmp[0];
                int x = tmp[1];

                for (int j = 0; j < 4; j++) {
                    int yy = y + tmp1[j];
                    int xx = x + tmp2[j];

                    if (xx >= 0 && xx < M && yy >= 0 && yy < N && tomato[yy][xx] == 0) {
                        queue.add(new int[]{yy, xx});
                        tomato[yy][xx] = 1;
                        cnt++;
                    }
                }
            }

            if (cnt == 0) {
                for(int i = 0; i < N; i++) {
                    for(int j = 0; j < M; j++) {
                        if(tomato[i][j] == 0) {
                            System.out.println(-1);
                            return;
                        }
                    }
                }
                System.out.println(day);
                return;
            }

            day++;
        }

        System.out.println(day);
    }

}

첫 풀이의 아래 부분이 맘에 들지 않았다. 굳이 이중반복문을 돌려 체킹을 할 필요가 있을까?

if (cnt == 0) {
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(tomato[i][j] == 0) {
                System.out.println(-1);
                return;
            }
        }
    }
    System.out.println(day);
    return;
}

그리하여 아래와 같이, 미리 totalTomato 개수를 선정하여, 익혀야 하는 토마토의 개수를 나타내주었고 아래와 같이 조건을 변경하였다.

if (cnt == 0) {
    if (totalTomato == 0) System.out.println(day);
    else System.out.println(-1);
    return;
}

아래는 바꾼 전체코드

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 BaekJoon7576 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int totalTomato = N * M;

        int[][] tomato = new int[N][M];
        Queue<int []> queue = new LinkedList<>();
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            for(int j = 0; j < M; j++) {
                int number = Integer.parseInt(st.nextToken());
                tomato[i][j] = number;

                if(number == 1) {
                    queue.add(new int[] {i, j});
                    totalTomato--;
                }
                else if(number == -1) totalTomato--;
            }

        }

        int day = queue.isEmpty() ? -1 : 0;
        int[] tmp1 = new int[] {1, -1, 0, 0};
        int[] tmp2 = new int[] {0, 0, 1, -1};

        while(!queue.isEmpty()) {
            int size = queue.size();
            int cnt = 0;

            for (int i = 0; i < size; i++) {
                int[] tmp = queue.poll();
                int y = tmp[0];
                int x = tmp[1];

                for (int j = 0; j < 4; j++) {
                    int yy = y + tmp1[j];
                    int xx = x + tmp2[j];

                    if (xx >= 0 && xx < M && yy >= 0 && yy < N && tomato[yy][xx] == 0) {
                        queue.add(new int[]{yy, xx});
                        tomato[yy][xx] = 1;
                        totalTomato--;
                        cnt++;
                    }
                }
            }

            if (cnt == 0) {
                if (totalTomato == 0) System.out.println(day);
                else System.out.println(-1);
                return;
            }
            day++;
        }

        System.out.println(-1);
    }

}

이중반복문을 돌리기 싫어서 바꿔줬는데, 사실 시간복잡도 측면에서 크게 차이는 없다. (N,M <= 1,000 이다)