[BAEKJOON] - 7576번 : 토마토

7576번 문제 링크

📜 알고리즘 접근 방법

해당 문제는 BFS 또는 DFS로 접근 가능한 문제입니다.

필자는 BFS를 사용하여 구현하였습니다.

대표적인 그래프 완전 탐색 문제입니다. 주의할 점은 다음과 같습니다.

전파 : 안익은 토마토가 익는 것

• 대각선은 전파가 발생하지 않고 위, 아래, 오른쪽, 왼쪽으로만 발생합니다.

• 박스의 크기를 염두하여 구현해야 합니다.( m * n)

  if (row >= 0 && col >= 0 && col < n && row < m) { ... }

• 익은 토마토(전파 시작점)의 2개 이상의 위치에서 동시에 전파가 발생합니다.

• 익은 일수를 대입 시, 기준 일수보다 1이 더 크게 됩니다. 예를 들면, 다음과 같이 구현되도록 하므로, 실제 지난 일수보다 1이 더 커지게 됩니다.

  1 0 -> 1 2(실제 1일) -> 1 2 3(실제 2일) -> ...
  0	   2(실제 1일)      2 3(실제 2일)

  		// 0인 경우에만 전파
  		if (box[col][row] == 0) {
  			q.offer(new int[] { col, row });
  			box[col][row] = box[c][r] + 1; // 이전 위치에 더하기 1
  		}

👾 성공

import java.util.*;
import java.io.*;

public class Main {
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };
    static int[][] box; // 박스
    static int count = 0; // 최소 날짜
    static int m, n; // 가로, 세로
    static Queue<int[]> q = new LinkedList<>(); // 익은 토마토 인덱스

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sArr = br.readLine().split(" ");
        
        // 전역 변수 초기화
        m = Integer.parseInt(sArr[0]);
        n = Integer.parseInt(sArr[1]);
        box = new int[n][m];

		// box 및 익은 토마토 인덱스 초기화
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                box[i][j] = Integer.parseInt(st.nextToken());
                if (box[i][j] == 1)
                    q.offer(new int[] { i, j });
            }
        }

        br.close();

        System.out.println(bfs());
    }

    static int bfs() {
		// 익은 토마토의 인덱스를 poll 하여 좌, 우, 위, 아래 탐색
        while (!q.isEmpty()) {
            int[] idx = q.poll();
            int c = idx[0];
            int r = idx[1];

            for (int i = 0; i < 4; i++) {
                int col = c + dx[i];
                int row = r + dy[i];

                if (row >= 0 && col >= 0 && col < n && row < m) {
                	// 0인 경우에만 전파
                    if (box[col][row] == 0) {
                        q.offer(new int[] { col, row });
                        box[col][row] = box[c][r] + 1;
                    }
                }

            }
        }

		// 안익은 토마토 있는지 재탐색 및 전체 일 수 중 max 값으로 초기화
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (box[i][j] == 0)
                    return -1;

                count = Math.max(count, box[i][j]);
            }
        }

        if (count == 1) {
            return 0;
        } else {
            return count - 1; // 초기값이 1부터 시작하기 때문에 -1해준 일수를 반환
        }
    }
}