99클럽 코테 스터디 12일차 TIL + BFS(C++)

문제

[백준] 7576번: 토마토

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

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int M, N;                   // M: 가로(열), N: 세로(행)
int visited[1001][1001];    // 토마토가 익은 날짜를 저장하는 배열
int tomato[1001][1001];     // 토마토가 저장된 상자의 상태를 저장하는 배열
queue<pair<int, int>> q;    // BFS를 위해 (x, y) 좌표를 저장하는 큐
int ans;                    // 모든 토마토가 익기까지 걸리는 최대 날짜

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

void bfs() {
    while (!q.empty()) {
        auto [x, y] = q.front(); // (x, y): 현재 익은 토마토의 좌표
        q.pop();

        // 현재 위치에서 네 방향으로 탐색
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || nx >= N || ny < 0 || ny >= M)
                continue;

            // 익지 않은 토마토(0)이고 아직 방문하지 않은 경우
            if (tomato[nx][ny] == 0 && visited[nx][ny] == -1) {
                visited[nx][ny] = visited[x][y] + 1; // 익은 날짜 갱신
                q.push({nx, ny});
            }
        }
    }
}

int main() {
    cin >> M >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            // 각 칸의 토마토 상태 입력 (1: 익은 토마토, 0: 익지 않은 토마토, -1: 토마토 없음)
            cin >> tomato[i][j]; 
            // 방문 배열을 -1로 초기화 (방문하지 않았음을 표시)
            visited[i][j] = -1;

            if (tomato[i][j] == 1) { // 익은 토마토인 경우
                q.push({i, j});      // 큐에 위치를 삽입하여 익은 토마토를 BFS의 시작점으로 설정
                visited[i][j] = 0;   // 익은 토마토가 있는 위치는 0일 차로 설정
            }
        }
    }

    // BFS 실행
    bfs();

    // 모든 토마토가 익을 때까지 걸린 날짜 계산
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            ans = max(ans, visited[i][j]); // 가장 오래 걸린 날짜 찾기

            // 익지 않은 토마토가 존재하는지 확인
            if (tomato[i][j] == 0 && visited[i][j] == -1) {
                cout << -1; // 익지 않은 토마토가 있으면 -1 출력 후 종료
                return 0;
            }
        }
    }

    cout << ans; // 모든 토마토가 익기까지 걸린 날짜 출력

    return 0;
}

 

풀이

이 문제는 세 가지 핵심 포인트를 고려하여 코드를 작성해야 한다.

 

1. 토마토 상태별 배열값 저장

N*M번 동안 토마토의 상태를 입력받는다. 토마토의 상태는 익은 토마토(1), 익지 않은 토마토(0), 토마토가 들어있지 않은 칸(-1) 세 가지로 나뉜다.

이때, 각 상태별로 visited 배열에 저장되는 값을 구분하는 것이 중요하다. 이는 나중에 익지 않은 토마토의 존재 여부를 확인하기 위함이다.

모든 위치에 대해 visited는 -1로 초기화된다. 그러나 익은 토마토(1)를 입력받은 경우, visited 배열을 0으로 설정한다.

이렇게 하면 익은 토마토는 tomato[i][j] = 1, visited[i][j] = 0이 되고, 익지 않은 토마토는 tomato[i][j] = 0, visited[i][j] = -1로 각 배열값이 구분되어 저장된다.

 

2. BFS 함수

예제3을 보면 (0, 0), (3, 5) 위치에 익은 토마토(1)가 있다.

이처럼 익은 토마토가 두 개 이상 존재할 수 있으므로, N*M번 동안 토마토가 저장된 배열을 순회하며 익은 토마토를 발견할 때마다 BFS를 실행하면 안 된다.

두 개 이상의 익은 토마토가 첫날부터 동시에(엄밀히 말하면 동시는 아니지만) 익어가야 하기 때문에,

배열 순회 중 익은 토마토를 발견하면 즉시 BFS를 실행하지 않고, 우선 큐에 익은 토마토의 좌표를 저장해야 한다.

이렇게 익은 토마토들의 좌표를 먼저 큐에 저장한 후, 배열 순회를 마치고 BFS를 실행하여 서로 다른 위치에 있는 익은 토마토들이 함께 익어가도록 구현하는 것이 핵심이다.

 

3. 토마토들이 익기까지의 최소 날짜 구하기

BFS가 종료되면 토마토들이 익기까지의 최소 날짜를 구해야 한다.

토마토가 저장된 배열을 순회하면서 visited[i][j]의 값으로 ans 변수에 최소 날짜를 갱신한다. 이때 익지 않은 토마토가 존재한다면 -1을 출력하고 종료한다.

처음부터 모든 토마토가 익어있었다면 ans 값은 변하지 않고 초기값인 0을 유지할 것이다.

따라서 익지 않은 토마토가 없다면, 즉 토마토가 모두 익었거나 처음부터 모두 익어있었다면 그대로 ans를 출력하고 종료한다.