(10) [C++, Java] 백준 No.7576 : 토마토

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/400

 

# C++

#include<cstdio>
#include<queue>
using namespace std;

int place[1001][1001];  // -1 : 이동할 수 없는 칸, 0 : 이동할 수 있는 칸, 1 : 이동할 수 있는 칸
int dist[1001][1001];   // -1 : 방문하지 않음, 0 이상은 방문했으며 익은 토마토 로부터의 거리를 의미
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int w, h;


int main()
{
    // 데이터 입력받기
    scanf("%d %d", &w, &h);

    // 사용전 배열 초기화
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            place[i][j] = 0;
            dist[i][j] = -1;
        }
    }

    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            scanf("%d", &place[i][j]);
        }
    }

    //여러개의 시작점을 큐에 넣어줌.
    queue<pair<int, int>> q;

    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            if(place[i][j] == 1){
                q.push(make_pair(i, j));
                dist[i][j] = 0;
            }
        }
    }

    //BFS탐색 시작
    while(!q.empty()){
        pair<int, int> p = q.front();
        q.pop();
        int cx = p.first;
        int cy = p.second;

        for(int k = 0; k < 4; k++){
            int nx = cx + dx[k];
            int ny = cy + dy[k];

            if(nx >= 1 && nx <= h && ny >= 1 && ny <= w){
               // printf("%d %d*\n", nx, ny);
               // printf("%d %d*\n", place[nx][ny], dist[nx][ny]);

                if(place[nx][ny] == 0 && dist[nx][ny] == -1){
                    q.push(make_pair(nx, ny));
                    dist[nx][ny] = dist[cx][cy] + 1;
                }
            }
        }
    }

    //최대값 구하기
    int ans = 0;
    bool is_all_done = true; // 존재하는 토마토가 다 익었나

    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            if (ans < dist[i][j])
                ans = dist[i][j];

            if (dist[i][j] == -1 && place[i][j] == 0)
                is_all_done = false;
        }
    }

    if (is_all_done){
        printf("%d\n", ans);
    }
    else{
        printf("-1\n");
    }
}

# Java

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);
    }
}