[BOJ알고리즘, C++]#7576_토마토, 그래프 탐색, BFS

 

#1. 문제

7576번: 토마토

 

---

 

#2. 풀이

 

1. 그래프 탐색, BFS

[자료구조]#6_그래프

 

BFS(너비 우선 탐색)은 그래프 내 모든 정점을 탐색하는 방법 중 하나로 현재 정점의 인접 정점들을 우선적으로 탐색하는 방법입니다. 일반적으로, BFS는 큐 자료구조를 활용하여 구현 가능합니다.

 

2. 가장 먼저, 익은 토마토 위치를 모두 큐에 넣어놓자!

 

1. 먼저, 익은 토마토 위치를 pair로 묶어 큐 자료구조에 삽입해 줍니다.
2. 다음으로, BFS를 수행하며 익은 토마토와 인접해 있는 안 익은 토마토들을 '익은 토마토'로 업데이트하고, 그 날짜를 기억해 줍니다.
3. 다시 한번, 상자의 모든 위치를 순회하며 안 익은 토마토가 있는지 확인하고, 결과를 출력합니다.

 

---

 

#3. 코드

 

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

typedef pair<int, int> p;

int N, M;
vector<vector<int>> box;
queue<p> q;

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

void bfs()
{
    while (!q.empty())
    {
        int cy = q.front().first;
        int cx = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int ny = cy + dy[i];
            int nx = cx + dx[i];

            if (ny < 0 || ny >= N || nx < 0 || nx >= M || box[ny][nx] != 0)
                continue;

            box[ny][nx] = box[cy][cx] + 1;
            q.push(make_pair(ny, nx));
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> M >> N;

    box.resize(N, vector<int>(M));

    // #1. 익은 토마토의 위치를 모두 큐에 삽입해줍니다.
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            cin >> box[i][j];
            if (box[i][j] == 1)
                q.push(make_pair(i, j));
        }
    }

    // #2. bfs를 수행하며, 주변 안익은 토마토들의 익게된 날짜를 기록해줍니다.
    bfs();

    // #3. 안익은 토마토가 존재하는지 확인하고, 최대 일자를 기록합니다.
    int result = 0;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (box[i][j] == 0)
            {
                cout << -1;
                return 0;
            }
            result = max(result, box[i][j]);
        }
    }

    cout << result - 1;

    return 0;
}

 

---