• Home
  • About
    • JOOS photo

      JOOS

      Joos's blog

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
  • Projects

[백준] 7576번 : 토마토 with java

19 Oct 2018

Reading time ~1 minute

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

import java.util.*;

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

public class Main {

    private static Scanner sc = new Scanner(System.in);
    private static final int[] dx = {0, 0, 1, -1};
    private static final int[] dy = {1, -1, 0, 0};
    public static void main(String args[]) {
        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;
//                일단은 가지 않음 다 -1로 한다.

                if (a[i][j] == 1) {
                    q.add(new Pair(i, j));
//                    1인 것들을 다 저장한다.
                    dist[i][j] = 0;
//                    dist는 거리를 저장하는 것
                }
            }
        }
        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) {
//                        가지 않은 노드만 한다. -1인 것은 가지 않기 위해 a의 값이 0인 값만 if문에 넣는다.
                        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];
                    //        가장 큰 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){
//                    a[i][j]가 0이라는건 익을 가능성이 있는데 -1이면 가지 못했다.
                    ans = -1;
                }
            }
        }
        System.out.println(ans);
    }
}


algorithm백준java Share Tweet +1