[BOJ] 7576. 토마토(BFS)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

전에도 한 번 풀어보았던 토마토 문제다

저번에는 BFS와 DP의 콜라보(?)로 풀어보았는데

이번에는 BFS만으로 풀어보았다.

그래도 전에 풀었을 때보다 확실히 능숙하게 풀어낸 느낌이었다.

이미 풀어보았던 문제라서 그럴 수도 있지만

뭔가 막힘없이 풀려서 좋았따

캬핫

#. Code

#include <cstdio>
#include <queue>
using namespace std;
#define pos pair<int, int>
#define x first
#define y second
 
int map[1010][1010];
int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };
 
int main(void)
{
    int m, n, i, j, res = 0, cnt = 0;
    // freopen("input.txt", "rt", stdin);
    scanf("%d %d", &m, &n);
 
    queue<pos> Q;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            scanf("%d", &map[i][j]);
 
            if (map[i][j] == 1) {
                Q.push({ i,j });
                cnt++;
            }
        }
    }
 
    while (!Q.empty()) {
        int tmp = cnt;
        cnt = 0;
 
        for (j = 0; j < tmp; j++) {
            pos now = Q.front();
            Q.pop();
 
            for (i = 0; i < 4; i++) {
                int xx = now.x + dx[i];
                int yy = now.y + dy[i];
 
                if (map[xx][yy] == 0 && xx > 0 && xx <= n && yy > 0 && yy <= m) {
                    Q.push({ xx,yy });
                    map[xx][yy] = 1;
                    cnt++;
                }
            }
        }
 
        res++;
    }
 
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if (map[i][j] == 0) {
                printf("-1\n");
                return 0;
            }
        }
    }
 
    printf("%d\n", res - 1);
 
    return 0;
}

line 22) 입력받으면서 익은 토마토가 있는 위치를 Queue에 저장

     cnt 변수는 1일에 몇 개의 토마토를 확인해야하는지 확인하기 위해 두었다

line 29~50) Queue가 빌 때까지 반복

line 33~47) 당일 확인해야 할 토마토 개수만큼 반복

line 34~35) 확인할 토마토

line 37~46) 주변에 안 익은 토마토가 있는지 확인

line 41~45) 있다면

line 42) Queue에 넣어주고

line 43) 익혀주고

line 45) 다음날 확인해야 할 토마토의 개수를 cnt

line 49) 토마토를 익히는데 걸리는 날짜 cnt

line 52~59) 토마토 창고를 확인하면서 아직도 익지 않은 토마토가 있을 경우 '-1' 출력

    다 익었다면 익히는데 걸린 날짜를 출력

    ( 1을 빼준 이유는 첫 날도 cnt에 포함시켰으므로)