[백준알고리즘] 7576번 토마토

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

아니 이 빨간 줄 뭐죠..?....

나중에 다시 올려야 긋네..

queue에 pair로 인자 넣으니까 개꿀깨꿀*^^

내가 생각한 알고리즘이 한번에 맞아 들어간게 얼마만인가... 감격 ㅠㅠ

bfs로 풀었당!_!

조건에 따른 출력을 좀 더티하게 짠 것 같긴하다만...

#include<queue>
#include<iostream>
using namespace std;
 
int arr[1001][1001];
queue<pair<int, int>>q;
 
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
 
int main(void)
{
    // 처음부터 모두 익어있는 상태인가.
    // 0이 들어있지 않은가.
 
    int row, col, v = 0;
    int flag = 0;
    int cnt = 0;
 
    cin >> row >> col;
 
    for (int i = 0; i < col; i++)
    {
        for (int j = 0; j < row; j++)
        {
            cin >> v;
            if (v == 0) flag = 1;
            if (v == 1) q.push(make_pair(i,j));
            arr[i][j] = v;
        }
    }
 
    // flag가 0이면 처음부터 모두 익어있는 상태인 것이다.
 
    if (!flag) {
        printf("0"); return 0;
    }
 
    // 익은 토마토 : 1
    // 익지 않은 토마토 : 0
    // 토마토가 들어있지 않은 칸 : -1
 
    while (!q.empty())
    {
        int sz = q.size();
 
        while (sz--) {
 
            pair<int, int> p = q.front();
            q.pop();
 
            for (int i = 0; i < 4; i++)
            {
                int mx = p.first + dx[i];
                int my = p.second + dy[i];
                // 갈 수 있는 공간이고 그 공간이 익지 않은 토마토가 있는 곳이면
                if (mx >= 0 && mx < col && my >= 0 && my < row && arr[mx][my] == 0)
                {
                    // 토마토가 익는다.
                    arr[mx][my] = 1;
                    // 익은 토마토의 위치를 queue에 넣는다.
                    q.push(make_pair(mx, my));
                }
            }
        }
        cnt++;
    }
 
    for (int i = 0; i < col; i++)
    {
        for (int j = 0; j < row; j++)
        {
            if (arr[i][j] == 0) { printf("-1"); return 0; }
        }
    }
 
    printf("%d", cnt-1);
    return 0;
}