백준 7576번 토마토 G5 - BFS

 

 

엉ㅇ엉 오래걸렸어

 

 

요즘 지문 긴게 좋더라.. 뭔가 풀고 뿌듯한 느낌이 든다.

이해 잘못하면 큰일이긴 한데 ㅎㅎ

 

이 문제는 쉬운 BFS인데 시작점이 여러개라는 점과 날짜를 어떻게 기록하지? 가 관건인 문제였다.

익은 토마토 주변에 안익은 토마토가 있다면, 하루지나고 익어버린다. 다 익는 최소 날짜를 출력해야하고, 못익거나 처음부터 다 익은 경우는 각각 -1, 0을 출력하면 된다.

 

날짜 출력이 관건인데 이를 +1로 해결했다.

이 방법을 찾지못해서 온갖 방법을 쓰다가 결국 남의 블로그들을 뒤져보았다 호호 ㅠㅠ

익은 토마토 근처에 토마토가 있다면, 익은 토마토의 값 +1을 해주어 마지막 토마토값을 출력하면 날짜가 되었다.

 

로직을 자연어로 정리하면

1. 익은 토마토 1을 발견하면 Que에 넣는다.

2. Que가 빌때까지 반복한다.

- 범위를 체크한다. 주변에 안익은 토마토인 0이 존재한다면 해당 토마토 위치를 Que에 넣고

arr에 익은 토마토 + 1값을 넣어준다.

 

하지만 이건 너무 쉽지 않은가. 고려해야 할것이 있었다.

단순히 1을 찾아서 큐에 넣고 로직을 돌리는게 아니라, 모든 1을 넣고 로직을 돌려야 했다.

왜냐면 익은 토마토 주변은 동시에 익어야하기 때문이다. 기존 로직처럼 돌렸다면

//		6 4
//		1 -1 0 0 0 0
//		0 -1 0 0 0 0
//		0 0 0 0 -1 0
//		0 0 0 0 -1 1
//
//		1 -1 7 8 9 10 
//		2 -1 6 7 8 9 
//		3 4 5 6 -1 10 
//		4 5 6 7 -1 1

이처럼 0,0의 1이 먼저 큐에 들어가는 바람에 최소 날짜가 10이 출력이 되었다.

 

import java.util.*;
 
public class Main { // 백준 7576번 토마토 G5
    // 1찾으면 큐에 넣기. 주변에 0 있으면 2로 변경
    // 토마토 중 높은 숫자 넣기
    public static int[] dr = { -1, 1, 0, 0 };
    public static int[] dc = { 0, 0, -1, 1 };
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int N = sc.nextInt();
        int M = sc.nextInt();
        int arr[][] = new int[M][N];
        Queue<int[]> que = new LinkedList<>();
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                arr[i][j] = sc.nextInt();
                if (arr[i][j] == 1) {
                    que.add(new int[] { i, j });
                }
            }
        }
        // 0 은 안익은 토마토, 1은 익은 토마토, -1은 없는 토마토.
        while (!que.isEmpty()) {
            int[] cur = que.poll();
            int r = cur[0];
            int c = cur[1];
            for (int k = 0; k < 4; k++) {
                int next_r = r + dr[k];
                int next_c = c + dc[k];
 
                if (next_r >= 0 && next_c >= 0 && next_r < M && next_c < N) {
                    if (arr[next_r][next_c] == 0) {
                        que.add(new int[] { next_r, next_c });
                        arr[next_r][next_c] = arr[r][c] + 1;
                    }
                }
            }
        }
 
        int answer = Integer.MIN_VALUE;
        Loop1: for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 0) {
                    answer = -1;
                    break Loop1;
                }
                answer = Math.max(answer, arr[i][j]);
            }
        }
 
        if (answer == 1) {
            System.out.println(0);
        } else if (answer == -1) {
            System.out.println(-1);
        } else {
            System.out.println(answer-1);
        }
 
        // 아 큐 순서에따라 값이 다르더라, 큐에 넣는거랑 로직이랑 분리하자.
//        6 4
//        1 -1 0 0 0 0
//        0 -1 0 0 0 0
//        0 0 0 0 -1 0
//        0 0 0 0 -1 1
//
//        1 -1 7 8 9 10 
//        2 -1 6 7 8 9 
//        3 4 5 6 -1 10 
//        4 5 6 7 -1 1 
 
    }
 
}

 

찍어보는 습관이 중요한것 같다. 안찍어봤으면 어디 숫자 잘못 들어갔나.. 했겠네