백준 7576 풀이

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

토마토

풀이 과정

익은 토마토(1) 주변의 익지 않은 토마토(0)을 익게 만들어야 한다.

익은 토마토를 기준으로 상하좌우의 익지 않은 토마토를 익게 하기때문에 bfs를 써야한다.

그런데 이 때 주의해야할 점이 익은 토마토 주변의 익지 않은 토마토가 동시에 익는다는 것이다.

일반적인 bfs로는 금방 익지 않은 토마토를 익게 만들 수 있었지만 최소 일수를 구하는데 어려움이 있었다.

그래서 처음에는 큐에 1인 좌표를 넣고 bfs를 실행, 다른 큐에 익을 수 있는 토마토의 좌표를 저장해서 재귀호출을 하는 방식으로 풀었다.

이렇게해서 답은 구했지만 메모리 낭비가 있고, 이런 부분이 맘에 들지 않았다. 그래서 더 나은 해답을 구하기위해 검색을 했고 나은 해답을 찾았다.

풀이

1. 좌표의 값이 1인 좌표를 큐에 저장
2. bfs를 통해 확장한 좌표를 찾아 다른 큐에 저장
   2-1.저장이 끝나면 day증가
3. bfs를 큐를 매개변수로 재귀 호출
4. 2~3 반복
5. 모든 좌표에 1로 가득차면 bfs 종료

기존 풀이는 위와 같았다. 이후 검색을 통해 아래와 같이 개선했다.

1.좌표의 값이 1인 좌표들을 큐에 저장
2. bfs를 통해 확장한 좌표를 큐에 저장
3. 확장한 좌표의 값을 확장하기 전 좌표의 값+1로 지정
4. 큐가 빌때까지 반복(모든 좌표에 1로 가득참)
5. 그래프에서 최대값을 찾는다.
6. day는 0일부터 출발하고 그래프의 출발점은 1부터 시작했기때문에 1을 빼고 출력

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static boolean visit[][];
    static int n, m;
    static int graph[][];
    //static int day = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input = br.readLine().split(" ");
        m = Integer.parseInt(input[0]);
        n = Integer.parseInt(input[1]);
        graph = new int[n][m];
        visit = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(line[j]);
            }
        }

        Queue<Pair> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (graph[i][j] == 1) {
                    queue.offer(new Pair(i, j));
                }
            }
        }

        int ans = 0;
        if (!isZero())
            ans = 0;
        else {
            tomato(queue);
            for(int i = 0;i<n;i++){
                for(int j = 0;j<m;j++)
                    ans = Math.max(ans, graph[i][j]);
            }
            ans = ans -1;
        }
        if (isZero()) {
            ans = -1;
        }
        bw.write(ans + "\n");
        br.close();
        bw.close();
    }

    private static void tomato(Queue<Pair> queue) {
        //Queue<Pair> tmp = new LinkedList<>();
        while (!queue.isEmpty()) {
            Pair p = queue.poll();
            int x = p.x;
            int y = p.y;
            visit[x][y] = true;
            for (int i = 0; i < 4; i++) {
                if ((x + dx[i] >= 0 && x + dx[i] <= n - 1) && (y + dy[i] >= 0 && y + dy[i] <= m - 1)) {
                    if (graph[x + dx[i]][y + dy[i]] == 0 && !visit[x + dx[i]][y + dy[i]]) {
                        graph[x + dx[i]][y + dy[i]] = graph[x][y] + 1;
                        visit[x + dx[i]][y + dy[i]] = true;
                        queue.offer(new Pair(x+dx[i], y+dy[i]));
                        //tmp.offer(new Pair(x + dx[i], y + dy[i]));
                    }
                }
            }
        }
        /*if(!tmp.isEmpty()) {
            day++;
            tomato(tmp);
        }
        else
            return;*/
    }

    private static boolean isZero() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (graph[i][j] == 0)
                    return true;
            }
        }
        return false;
    }

    private static void printGraph() {
        for (int[] arr : graph) {
            for (int a : arr)
                System.out.print(a + " ");
            System.out.println();
        }
    }
}

class Pair {
    public int x;
    public int y;

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