[백준] 7576 토마토 - 자바

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

7576번: 토마토

문제 풀이

현재 좌표에서 상하좌우로 즉 인접한 좌표를 탐색하기 때문에 bfs를 통해 해결할 수 있다.

 

먼저 좌표 상 -1로 빈 공간이 있기 때문에 전부 다 익은 토마토인지 비교하기 위해 빈공간의 갯수를 체크해줘야 한다.

또한 Queue를 통해 익은 토마토를 하나씩 꺼내 인접한 토마토를 익게하며, queue에 모든 요소를 다 꺼내서 이 과정을 수행하는 게 한 사이클이다. 이해가 안 가더라도 이후 코드를 참고하자

// init()
for (int i = 0; i < N; i++) {
    st = new StringTokenizer(br.readLine());
    for (int j = 0; j < M; j++) {
        int now = Integer.parseInt(st.nextToken());
        board[i][j] = now;

        if (now == 1)
            ripeTomatoes.offer(new Tomato(i, j));
        if (now == -1)
            emptyCnt++;
    }
}

다음으로 상하좌우를 살피기 위한 좌표코드이다

static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};

위에서 언급했듯이 빈 공간이 생기기 때문에 익은 토마토의 갯수를 업데이트 해줘야 한다.

좌표가 4*6일 때 빈 공간이 3개라면 익은 토마토가 21개일 때 모든 토마토가 익은 토마토임을 확인할 수 있다

int depth = -1; // 맨 처음 익은 토마토를 꺼내는 행위는 기존에 있던 토마토를 꺼내기 때문에 -1부터 시작
int ripeTomatoesSize = ripeTomatoes.size(); // 익은 토마토 갯수 카운트

하루가 지나면 모든 익은 토마토가 상하좌우로 영향을 준다. 따라서 while문의 한 사이클은 '모든' 익은 토마토가 옆으로 영향을 줄 때 하루가 지난다. 따라서 while 반복문의 사이클은 for문을 통해 모든 익은 토마토를 꺼냈을 때이다. 이 과정이 반복되는 것이다.

static Queue<Point> ripeTomatoes = new LinkedList<>();

while (!ripeTomatoes.isEmpty()) {
    depth++;
    int size = ripeTomatoes.size(); // for문 안의 ripeTomatoes에 요소를 추가하는 ripeTomatoes.offer가 있기 때문에
                                    // for 조건문의 바로 size()메소드를 쓰면 연산 횟수가 꼬임

    for (int i = 0; i < size; i++) {
        Point now = ripeTomatoes.poll();
        for (int j = 0; j < 4; j++) {
            int nx = now.x + dx[j];
            int ny = now.y + dy[j];

            // 범위를 벗어나거나, 0이 아닌 경우는 제외
            if (outOfScope(nx, ny) || board[nx][ny] != 0)
                continue;

            board[nx][ny] = 1;
            ripeTomatoesSize++;
            ripeTomatoes.offer(new Tomato(nx, ny));
        }
    }
}

static boolean outOfScope(int nx, int ny) {
    if (nx < 0 || ny < 0 || nx >= N || ny >= M)
        return true;
    return false;
}

코드

package 백준;

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

class Tomato {
    int x;
    int y;

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

public class b7576 {
    static int N, M;
    static int[][] board;
    static Queue<Tomato> ripeTomatoes = new LinkedList<>();
    static int emptyCnt = 0;
    static int fullSize;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        board = new int[N][M];

        // init()
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int now = Integer.parseInt(st.nextToken());
                board[i][j] = now;

                if (now == 1)
                    ripeTomatoes.offer(new Tomato(i, j));
                if (now == -1)
                    emptyCnt++;
            }
        }

        fullSize = N * M;
        System.out.println(ripeTomatoes.size() == fullSize ? "0" : bfs());
    }

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int bfs() {
        int depth = -1; // 맨 처음 익은 토마토를 꺼내는 행위는 기존에 있던 토마토를 꺼내기 때문에 -1부터 시작
        int ripeTomatoesSize = ripeTomatoes.size(); // 익은 토마토 갯수 카운트

        while (!ripeTomatoes.isEmpty()) {
            depth++;
            int size = ripeTomatoes.size(); // for문 안의 ripeTomatoes에 요소를 추가하는 ripeTomatoes.offer가 있기 때문에
                                            // for 조건문의 바로 size()메소드를 쓰면 연산 횟수가 꼬임

            for (int i = 0; i < size; i++) {
                Tomato now = ripeTomatoes.poll();
                for (int j = 0; j < 4; j++) {
                    int nx = now.x + dx[j];
                    int ny = now.y + dy[j];

                    // 범위를 벗어나거나, 0이 아닌 경우는 제외
                    if (outOfScope(nx, ny) || board[nx][ny] != 0)
                        continue;

                    board[nx][ny] = 1;
                    ripeTomatoesSize++;
                    ripeTomatoes.offer(new Tomato(nx, ny));
                }
            }
        }
        return ripeTomatoesSize == fullSize - emptyCnt ? depth : -1;
    }

    static boolean outOfScope(int nx, int ny) {
        if (nx < 0 || ny < 0 || nx >= N || ny >= M)
            return true;
        return false;
    }
}