백준, BOJ, 7576번 C++ [CPP]

 

이것도 BFS의 기본이라고 볼 수 있다.

www.acmicpc.net/problem/7576

7576번: 토마토

 

 

---

 

 

이전 문제의 최단경로의 경로문제라고 해도 무방하다.

하지만 약간 꼬아놨으니

BFS의 시작점이 여러군데다.

 

근데 뭐 별다를 거 없다.

시작점을 큐에 다 넣고 시작하는 것과 같이

얘도 똑같이 해주면 된다.

 

#맞는 풀이

다만 최적화는 되어있지 않은 풀이

#include<iostream>
#include<queue>

#define X first
#define Y second

using namespace std;

int visit[1002][1002];
int box[1002][1002];

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


int n, m;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    queue<pair<int, int>> Q;

    int day = 0;
    cin >> m >> n;
    bool check = true;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> box[i][j];
            visit[i][j] = -1;


            //익은 토마토의 위치파악 -> BFS가 시작할 위치
            if (box[i][j] == 1) {
                Q.push({i, j});
                visit[i][j] = 0;
            }
        }
    }

    while (!Q.empty()) {
        auto cur = Q.front();
        Q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = cur.X + dx[i];
            int ny = cur.Y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                continue;
            if (visit[nx][ny] >= 0 || box[nx][ny] == -1)
                continue;
            visit[nx][ny] = visit[cur.X][cur.Y] + 1;
            day = visit[nx][ny];
            Q.push({nx, ny});
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (box[i][j] == 0 && visit[i][j] == -1){
                cout << -1;
                check = false;
                break;
            }
        }
        if (!check)
            break;
    }


    if (check)
        cout << day;

}

 

 

---

 

핵심은 시작점을 찾는 것.

또한 이 문제에서는 조건 몇 개 더

BFS가 방문하지 못하는 노드를 찾는 것

방문하지 못하는 이유가 있는가? -> 방문하지 못하는 노드의 특징(구분을 어떻게 할 것인가)

 

이 3가지를 파악하고 풀면 된다.