[백준] 7576 토마토

1. 문제

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

7576번: 토마토

2. 접근방법

bfs를 이용해 토마토를 익혀 가고

더 이상 익힐 토마토가 없다면

 

전체 map을 조사해서 아직 안익은 토마토가 있는지 확인 후,

-1 또는 익히는 데 든 시간을 print하면 된다.

 

3. 자바 코드

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

public class Main {

    static class Node {
        int row;
        int col;

        Node(int row, int col) {
            this.row = row;
            this.col = col;
        }

    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int map[][] = new int[N][M];
        Queue<Node> queue = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 1) {
                    queue.add(new Node(i, j));
                }
            }
        }
        int dr[] = new int[]{-1, 1, 0, 0};
        int dc[] = new int[]{0, 0, -1, 1};

        int day = -1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                Node now = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int row = now.row + dr[i];
                    int col = now.col + dc[i];
                    if (row < 0 || col < 0 || row >= N || col >= M) continue;
                    if (map[row][col] != 0) continue;
                    map[row][col] = 1;
                    queue.add(new Node(row,col));
                }
            }
            day++;
        }

        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < M ; j++){
                if(map[i][j] == 0) day = -1;
            }
        }

        System.out.println(day);
    }
}

4. 마치며

옛날에 틀리고 까먹고 있던 문제인데

내배캠에 있어서 다시 풀어봤다.

 

지금 풀어보니 bfs 활용하면 어렵지 않게 풀이 가능한데

그때는 M N 의 row col이 헷갈렸던게 아닐까 싶다.