7576번 : 토마토

안익은 토마토는 대충 버리지 왜 이런 시뮬레이션을...

 

원래 예전에 풀었던 문제들 중에 오답률 높은 것, 기억에 남는 것 위주로 포스팅하고 요즘 풀고있는 문제들을 올리려 하였으나

이건 풀다가 승질이 뻗쳐서 먼저 정리한다.

 

익은 토마토(1)은 주변 4방향으로 전파가 되고 안익은 0을 1로 바꿀 수 있다.

그리고 -1은 비어있는 토마토 이기 때문에 미로에서의 벽과 같은 역할을 한다.

 

다시말해 그냥 미로찾기 문제고, "모든 곳이 다 익었는지"는 모든 미로를 전부 탐험했는지랑 같다.

 

다음과 같은 과정을 거쳐야한다.

 

1. 모든 위치를 방문해야하고(방문해야 토마토가 익은 거니까)

2. 방문하고 났으면 얼마만에 방문한건지(며칠만에 익은건지 확인하기 위해서)

3. 가장 마지막에 방문한 노드의 방문 순서가 계산가능한 최소 시간이다.

 

즉 BFS를 이용하여 최단 경로를 계산하는 문제라고 생각했다만...

낮은 정답률에서 알 수 있듯이 문제는 그게 아니다.

 

일단 방문 할 수 없는 위치가 존재 할 수도있다.

 

전부 익히는 것이 불가능 한 경우

위와 같은 경우 외곽의 토마토는 우상단의 토마토를 통해 다 익을 수 있지만

좌상단의 토마토는 가까운 익은 토마토가 위치 할 수 없어 모든 토마토가 익지 않게된다.

 

.... 정도면 쉬운 문제였을 거고,

 

해결해야 하는 경우가 더 통수의 통수의 통수가 있다.

 

시작 위치가 여러 개인 예제

시작 위치가 여러개인 경우인데,

map상에서 익은 토마토가 map[0][0]과 map[3][5]에 있으니

map[1][0]과 map[3][4] 는 둘다 1이어야 하지만 섣불리 탐색을 시작하면 둘 중 한개는 1이아니라 10이 되어 버린다.

이런 반례가 있을 거라곤 예제에서 주지 않았더라면 상상도 못 했을거다. 

 

말로는 양쪽에서 동시에 출발하면된다고 하지만 어떻게 할지는 생각해내는데 꽤 오랜 시간이 걸렸다.

답은 의외로 간단했는데, 그냥 1(익은 토마토)의 위치를 BFS 돌리기전에 전부 큐에다가 넣어 놓는 것이었다.

그럼 BFS가 운영하는 큐는 아주 손쉽게 양쪽의 시작위치를 번갈아가면서 큐에다가 값을 넣고 탐색하기 때문에 쉽게 해결이 가능했다.

이거 생각 해내는데 한시간이 넘게 걸렸다.

 

좀더 문제를 바라보는 눈을 키워야겠다.

 

#include <iostream>
#include <queue>
#include <cstring>
 
using namespace std;
 
struct point
{
    int y;
    int x;
};
 
int N, M;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int visited[1000][1000];
queue<point> q;
point last;
 
void tomato();
 
int cnt = 0;
int main(int argc, char *argv[])
{
    cin>>M>>N;
 
    int t;
    for (int i=0; i<N; i++)
    {
        for (int j=0; j<M; j++)
        {
            cin>>t;
            if(t == 1)
            {
                visited[i][j] = 1;
                q.push({i, j});
            }
            if(t == -1)
                visited[i][j] = -1;
//            map[i][j] = t;
        }
    }
    
    if (q.empty())
        cout<<"-1\n";
    else
    {
        tomato();
        
        bool ismatured = true;
        for (int i=0; i<N; i++)
        {
            for (int j=0; j<M; j++)
            {
                if(visited[i][j] == 0)
                {
                    ismatured = false;
                    break;
                }
            }
            if(!ismatured)
                break;
        }
 
        if(ismatured)
            cout<<visited[last.y][last.x]-1<<"\n";
        else
            cout<<"-1\n";
    }
 
    return 0;
}
 
void tomato()
{
    if (q.empty())
        return;
    point p = q.front();
    q.pop();
    last = p;
 
    for (int i=0; i<4; i++)
    {
        if((visited[p.y+dy[i]][p.x+dx[i]] == 0) && \
           !(p.x+dx[i] < 0 || p.x+dx[i]>=M || p.y+dy[i] < 0 || p.y+dy[i]>=N))
        {
            q.push({p.y+dy[i], p.x+dx[i]});
            visited[p.y+dy[i]][p.x+dx[i]] = visited[p.y][p.x] + 1;
        }
    }
    
    tomato();
}