[백준][7576번] 토마토

문제 URL

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

전체 풀이

• 해당 문제는 브루트포스가 아닌 bfs를 이용해서 단계적으로 최소기한을 구할 수 있다.

package backjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;


public class Main {
    static public class Pair {
        public int x;
        public int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static final int[] dx = {0, 0, 1, -1};
    public static final int[] dy = {1, -1, 0, 0};

    public static void main(String args[]) throws IOException {
        String[] str = br.readLine().split(" ");
        int m = Integer.parseInt(str[0]);
        int n = Integer.parseInt(str[1]);
        // map[i][j] - i번째줄 j열, 익은 토마토는 1, 익지 않는 토마토는 0, 들어있지 않으면 -1
        int[][] map = new int[n][m];
        //방문 여부
        boolean[][] visit = new boolean[n][m];
        // dist[i][j] - 해당 토마토 익는데 걸린 시간
        int[][] dist = new int[n][m];

        for (int i = 0; i < n; i++) {
            str = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(str[j]);
                //토마토가 들어있않으면 -9로 초기화 그외는 -1로 초기화
                if(map[i][j] == -1)
                    dist[i][j] = -9;
                else
                    dist[i][j] = -1;
            }
        }

        // 저장될때부터 모든 토마토가 익어있는지 판단
        boolean fg = false;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(map[i][j] == 0){
                    fg = true;
                    break;
                }
            }
        }

        //모두 익어있으면 0출력후 종료
        if(!fg){
            System.out.println("0");
            return;
        }

        // 입력시 익어있는 토마토를 큐에 넣어 초기화해준다,.
        Queue<Pair> q = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 1) {
                    q.add(new Pair(j, i));
                    visit[i][j] = true;
                    dist[i][j] = 0;
                }
            }
        }

        //bfs
        while (!q.isEmpty()) {
            int x = q.peek().x;
            int y = q.peek().y;
            q.remove();

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (0 <= nx && nx < m && 0 <= ny && ny < n) {
                    if (visit[ny][nx] || map[ny][nx] == -1)
                        continue;
                    dist[ny][nx] = dist[y][x] + 1;
                    visit[ny][nx] = true;
                    q.add(new Pair(nx, ny));
                }
            }
        }

        // 모두 익을때까지의 최소 날짜를 계산
        int max = 0;
        boolean flag = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(dist[i][j] == -1){
                    flag = true;
                    break;
                }
                if (max < dist[i][j]) {
                    max = dist[i][j];
                }
            }
        }
        if(flag){
            System.out.println("-1");
        }else{
            System.out.println(max);
        }
    }
}

다른풀이

import java.util.*;

class Pair {
    int x;
    int y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static final int[] dx = {0, 0, 1, -1};
    public static final int[] dy = {1, -1, 0, 0};
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] a = new int[n][m];
        int[][] dist = new int[n][m];
        Queue<Pair> q = new LinkedList<Pair>();
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                a[i][j] = sc.nextInt();
                dist[i][j] = -1;
                if (a[i][j] == 1) {
                    q.add(new Pair(i, j));
                    dist[i][j] = 0;
                }
            }
        }
        while (!q.isEmpty()) {
            Pair p = q.remove();
            int x = p.x;
            int y = p.y;
            for (int k=0; k<4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
                if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                    if (a[nx][ny] == 0 && dist[nx][ny] == -1) {
                        q.add(new Pair(nx, ny));
                        dist[nx][ny] = dist[x][y] + 1;
                    }
                }
            }
        }
        int ans = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (ans < dist[i][j]) {
                    ans = dist[i][j];
                }
            }
        }
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (a[i][j] == 0 && dist[i][j] == -1) {
                    ans = -1;
                }
            }
        }
        System.out.println(ans);
    }
}