[백준 7576] 토마토

문제

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

7576번: 토마토

 

 

문제 분석 

토마토가 들어 있는 상자가 하나 있고, 한칸의 하나의 토마토 혹은 비어 있는 칸도 존재한다. 

 

익은 토마토는 위, 아래, 오른쪽, 왼쪽의 토마토를 익게할 수 있고, 비어있다면 익지 않는다. 

 

모든 토마토를 익게 하려면 얼마의 시간이 필요한지 구하는 문제이다. 

 

 

알고리즘 설계 

우선 입력을 받아 토마토를 담아둘 상자를 입력 받는다. 

 

1로 되어 익어있는 토마토는 queue에 넣어 관리해준다. 

 

BFS를 사용하여 좌, 우, 위, 아래를 확인하여 익은 토마토가 아니거나, 비어있지 않다면 익게 해준다. 만약 이 토마토가 익은 토마토 중 가장 최근에 익은 토마토라면 값을 갱신 시켜준다. 

 

BFS를 다 돌았다면 익지 않은 토마토가 존재하는지 확인하고 있다면 -1를 출력하고 끝내준다.

 

만약 다 익었다면 가장 최근에 익은 토마토를 출력한다. 

 

 

유의점

이중배열 및 이중벡터를 사용할때 x축과 y축을 잘 확인하여 만들어야한다. 

 

BFS에 대한 지식이 어느정도 존재해야한다. 

 

 

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int addX[] = { 1, -1, 0, 0 };
int addY[] = { 0, 0, 1, -1 };
vector<vector<int>> map;
queue<pair<int, int>> q;

int main()
{
    int n, m, lastIndex = 0;
    string str;
    cin >> m >> n;

    map.resize(n, vector<int>(m, 0));

    for (int j = 0; j < n; ++j)
    {
        for (int i = 0; i < m; ++i)
        {
            cin >> str;
            if (str == "-1")
            {
                map[j][i] = -1;
            }
            if (str == "1")
            {
                map[j][i] = 1;
                q.push(make_pair(j, i));
            }
        }
    }

    while (!q.empty())
    {
        int posY = q.front().first;
        int posX = q.front().second;
        q.pop();

        for (int i = 0; i < 4; ++i)
        {
            int x = posX + addX[i];
            int y = posY + addY[i];

            if (x < 0 || x >= m)
                continue;
            if (y < 0 || y >= n)
                continue;
            if (map[y][x] != 0)
                continue;
            if (map[y][x] == -1)
                continue;

            map[y][x] = map[posY][posX] + 1;
            if (lastIndex < map[y][x])
                lastIndex = map[y][x];
            q.push(make_pair(y, x));
        }
    }

    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (map[j][i] == 0)
            {
                cout << -1;
                return 0;
            }
        }
    }

    if (lastIndex == 0)
        cout << 0;
    else
        cout << lastIndex - 1;
    return 0;
}

 

입력 받을때 string이 아닌 int로 입력 받고, BFS 돌려줄때 if문 하나로 정리 해둔다면 좀 더 깔끔한 코드가 될 것 같다.