[JAVA] 백준 알고리즘 7576번 문제풀이 (토마토)

 

 

 

 

 

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

7576번: 토마토

 

 

 

 

● 토마토 (7576번) - BFS

 

 

 

 

 

 

 

import java.util.*;

class A {
    int x;
    int y;
    A(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<A> q = new LinkedList<A>();
        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 A(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);
    }
}

↓ 소스풀이 ↓

​

큐에 제네릭으로 넣어주기 위해 x,y 변수를 선언한 A클래스를 만들어줍니다.

그리고 Main클래스에서 입력을 n과m 변수를 선언해서 입력받아주고, dist배열은 만들어서 모두 -1로 초기화해줍니다.

dx과dy 배열은 익은토마토가 상,하,좌,우로만 안익은 토마토들을 익게 만들어준다고 했기에 만들어주었습니다.

토마토 상자에서 익은토마토(1)이 존재하면 큐 객체를 만들어주고, dist배열의 해당 행렬을 0을 저장해줍니다.

whlie을 이용해서 큐가 존재한다면 익은 토마토가 있다는 것이기에 상,하,좌,우 모두 익은 토마토로 만들어주는 작업을 진행했습니다.

익을때마다 일수를 체크해주기위해 dist배열에 익은 토마토가 있을때마다 +1을 해줍니다.

그리고 for 반복문을 사용해서 dist의 최대값을 구해서 ans에 저장해주고, 만약에 토마토가 모두 익지못하는 상황이라면 ans에 -1을 저장해주고 ans를 출력해줍니다.

 

 

 

< 백준알고리즘 강의를 보고 참고하였습니다! >

 

---