[백준/C,C++] 7576번: 토마토

www.acmicpc.net/problem/7576

7576번: 토마토

풀이

2차원 배열이 주어지는 여타 다른 BFS 문제들과 비슷합니다.

 

크게 다른 점은 출발 지점이 정해져 있지 않다는 건데요.

 

익은 토마토, 즉 1인 지점을 모두 시작 지점으로 BFS를 실행시켜야 한다는 겁니다.

 

6 4

1 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 1

 

과 같은 예제가 입력되었다고 봅시다.

 

1일이 지난 후 토마토들은 아래와 같게 됩니다.

 

1 1 0 0 0 0

1 0 0 0 0 0

0 0 0 0 0 1

0 0 0 0 1 1

 

2일이 지난 후는,

 

1 1 1 0 0 0

1 1 0 0 0 1

1 0 0 0 1 1

0 0 0 1 1 1

 

와 같죠.

 

즉, 모든 익은 토마토에서부터 BFS를 실행 시켜, 최대 깊이(depth)를 출력해주면 됩니다.

 

 

유의해야 할 점은 방문한 노드의 개수가 모든 노드의 개수와 다르다면

 

토마토가 모두 익지 못하는 상황이기에 -1을 출력해야 합니다.

 

#include<iostream>
#include<queue>

#define py first
#define px second

using namespace std;

const int MAX = 1000;

using PAIR = pair<int, int>;

int n, m;
int tomato[MAX][MAX];
queue<PAIR> q;
vector<PAIR> v;
PAIR d[4] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
int cnt[MAX][MAX];
int total, chk, res;

void visit(int y, int x)
{
    tomato[y][x] = 1;
    q.push(pair(y, x));
    chk++;
}

void BFS()
{
    size_t sz = v.size();
    
    for (size_t i = 0; i < sz; i++) {
        visit(v[i].py, v[i].px);
    }

    while (!q.empty()) {
        PAIR node = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = node.py + d[i].py;
            int nx = node.px + d[i].px;
            if (ny >= 0 && nx >= 0 && ny < m && nx < n) {
                if (tomato[ny][nx] != 1 && tomato[ny][nx] != -1) {
                    visit(ny, nx);
                    cnt[ny][nx] = cnt[node.py][node.px] + 1;
                    res = max(res, cnt[ny][nx]);
                }
            }
        }
    }
}

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

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> tomato[i][j];
            if (tomato[i][j] == 1) v.push_back(pair(i, j));
            if (tomato[i][j] != -1) total++;
        }
    }

    BFS();

    if (chk == total) cout << res;
    else cout << -1;

    return 0;
}

반례

Input

4 4

0 0 0 0

0 1 0 0

0 0 0 0

0 1 0 0

Output

3

 

Input

8 6
0 0 -1 0 0 0 0 1
1 0 0 0 0 0 0 -1
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 -1 -1 0 0 0 0

Output

6