Algorithm in A..Z - BFS

개념

그래프를 탐색할 때 인접한 노드를 우선적으로 탐색한다.

---

작동원리

1. Queue에 방문할 노드를 PUSH한다.

2. Queue에서 POP하고 인접한 노드를 Queue에 PUSH한다.

3. Queue가 비어있을 때까지 반복한다.

---

주의할 점

인접한 노드를 방문할 수 있는지 검사해야한다.

- 인덱스

- 방문여부

---

시간복잡도

O(V + E)

---

문제

7576 토마토

www.acmicpc.net/problem/7576

7576번: 토마토

---

코드

#include <bits/stdc++.h>
using namespace std;

constexpr int RIPED = 1;
constexpr int NOT_RIPED = 0;
constexpr int EMPTY = -1;

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

class Node {
public:
    int x, y;

    Node(int x = 0, int y = 0) : x(x), y(y) {

    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, m;
    cin >> m >> n;

    vector<vector<int>> map(n, vector<int>(m));
    for (auto &ve : map) {
        for (auto &i : ve) {
            cin >> i;
        }
    }

    int rest = 0;
    queue<Node> que;
    vector<vector<bool>> isVisited(n, vector<bool>(m, false));
    for (int y = 0;y < n;++y) {
        for (int x = 0;x < m;++x) {
            switch (map[y][x]) {
                case RIPED:
                    que.emplace(x, y);
                    isVisited[y][x] = true;
                    break;
                case NOT_RIPED:
                    rest++;
                    break;
            }
        }
    }

    int day = 0;
    while (!que.empty() && rest != 0) {
        auto k = que.size();
        while (k--) {
            auto now = que.front();que.pop();
            if (map[now.y][now.x] == NOT_RIPED) {
                rest--;
            }

            for (int i = 0;i < 4;++i) {
                int x = now.x + dx[i];
                int y = now.y + dy[i];

                if (x < 0 || x >= m || y < 0 || y >= n || isVisited[y][x] || map[y][x] == EMPTY) {
                    continue;
                }

                que.emplace(x, y);
                isVisited[y][x] = true;
            }
        }

        if (rest == 0) {
            break;
        } else {
            day++;
        }
    }

    if (rest) {
        cout << -1 << "\n";
    } else {
        cout << day << "\n";
    }
}