[백준] 7576 토마토(Gold.5) - BFS

문제

토마토

코드

큐 형태

큐에 좌표 뿐만 아니라 시간도 저장해야 하기 때문에 좌표와 시간을 멤버변수로 갖는 Node 클래스를 선언하고 Node 클래스를 큐의 자료형으로 선언했다.

class Node {
    int x, y, idx;

    Node(int x, int y, int idx) {
        this.x = x;
        this.y = y;
        this.idx = idx;
    }
}
static Queue<Node> q = new LinkedList<>();

 

위 입력 값을 큐에 삽입하면 아래 사진과 같이 삽입된다.

풀이 방법

1. 입력 받은 값을 2차원 배열에 넣고 1인 값의 좌표와 날짜(0일)을 큐에 삽입한다.

int[][] box = new int[M][N];
        for (int i = 0; i < M; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                box[i][j] = Integer.parseInt(input[j]);
                if (Objects.equals(input[j], "1")) {
                    q.offer(new Node(i, j, 0 ));
                }
            }
        }

2. BFS를 실행한다.
   1. 다른 BFS와 마찬가지로 상, 하, 좌, 우를 살펴보고 배열 내부이면서 값이 0인 경우 방문하고(box[cx][cy] = 1) 큐에 좌표와 현재 시간+1을 삽입한다.
   2. 이후 다시 반복을 진행하는데 새로운 토마토로 이동했으니 시간을 업데이트 해준다. if (node.idx != time) time++;
   3. 토마토가 들어있지 않은 칸(-1)으로 둘러 쌓인 경우 익지 못하는 토마토가 있는 경우 -1을 반환한다.

public static int bfs(int[][] box, int N, int M) {
        int time = 0;

        while (!q.isEmpty()) {
            Node node = q.poll();

            // -------------2-------------
            if (node.idx != time) // 1초가 지났을 경우
                time++;

            // -------------1-------------
            for (int i = 0; i < 4; i++) {
                int cx = node.x + dx[i];
                int cy = node.y + dy[i];
                if (cx >= 0 && cx < box.length && cy >= 0 && cy < box[0].length && box[cx][cy] == 0) {
                    box[cx][cy] = 1;
                    q.offer(new Node(cx, cy, time + 1));
                }
            }
        }

        // -------------3-------------
        // 토마토가 모두 익지는 못하는 상황 찾기 (-1에 둘러쌓인 경우)
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (box[i][j] == 0) {
                    return -1;
                }
            }
        }
        return time;
    }

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Node {
    int x, y, idx;

    Node(int x, int y, int idx) {
        this.x = x;
        this.y = y;
        this.idx = idx;
    }
}
public class _7576 {
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static Queue<Node> q = new LinkedList<>();
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 세로 칸 수
        int M = Integer.parseInt(st.nextToken()); // 가로 칸 수

        int[][] box = new int[M][N];
        for (int i = 0; i < M; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                box[i][j] = Integer.parseInt(input[j]);
                if (Objects.equals(input[j], "1")) {
                    q.offer(new Node(i, j, 0 ));
                }
            }
        }
        System.out.println(bfs(box, N, M));
    }

    public static int bfs(int[][] box, int N, int M) {
        int time = 0;

        while (!q.isEmpty()) {
            Node node = q.poll();

            if (node.idx != time) // 1초가 지났을 경우
                time++;

            for (int i = 0; i < 4; i++) {
                int cx = node.x + dx[i];
                int cy = node.y + dy[i];
                if (cx >= 0 && cx < box.length && cy >= 0 && cy < box[0].length && box[cx][cy] == 0) {
                    box[cx][cy] = 1;
                    q.offer(new Node(cx, cy, time + 1));
                }
            }
        }

        // 토마토가 모두 익지는 못하는 상황 찾기 (-1에 둘러쌓인 경우)
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (box[i][j] == 0) {
                    return -1;
                }
            }
        }
        return time;
    }
}