다시 말하지만 원본문제 자체의 유출은 금지라고 약관에 명시되어 있어서 동일 알고리즘 유사문제로 가져옴.

2번 문제는 위와 같은 형식의 문제. 어떠한 기준점이 몇개 주어지고, 그 기준점으로부터 전체가 영향을 받는데 얼마나 걸리는지 구하는 문제.

단, 삼성 문제는 위의 문제보다 쉬웠는데, 그 이유는 위의 문제처럼 토마토가 들어있지 않은 칸 등의 예외는 없었음.


아무튼 여기서는 예외를 포함해서 풀이를 하겠음.

얼핏 생각해보면, 가로 세로를 2중 for문으로 돌리면서 익은 토마토가 있으면 주변 토마토를 익었다고 표시를 해주고, 이 과정을 모두 다 익을 때까지

돌려서 구하면 되겠다 생각이 들겠지만, 이렇게 하면 특수한 경우 시간초과가 날 수도 있음.(1번의 2중 for문에 토마토가 1개씩만 익는 경우 등)

문제에서 M,N의 범위가 1000이기 때문에 1번 for문에 100만번의 연산이 수행되고, 토마토가 500개가 1번에 1개씩만 익는다면 5억번이 돌아가

시간초과. 따라서 이 문제는 for문이 아닌, BFS를 이용해서 풀어야 함.


BFS는 너비 우선 탐색이라는 뜻으로, DFS와 대비되는 개념. 쉽게 설명하면 DFS는 어떤 작업 도중 새로운 분기점이 발견되면 바로 거기로 들어가고,

BFS는 일단 새로운 분기점을 다음에 실행하겠다 예약을 해 두고 현재 작업을 모두 마치는 거임. DFS는 스택 기반이며 BFS는 큐 기반임.


처음 익은 토마토의 좌표를 찾아 큐에 등록을 해두고, 다음에는 토마토가 익게 하는 주변 토마토를 찾아 큐에 등록을 함.

단, 언제 익었는지 구분하기 위해 struct 등을 쓰거나 해서 토마토가 익은 날짜를 추가적으로 변수에 기록을 하는 것이 필요.


그렇게 해서 큐가 빌 때까지 모두 돌리면서 토마토가 익은 날짜 중 가장 큰 숫자를 저장해 두어 출력하면 됨.


#include<iostream>

#include<queue>

using namespace std;

int n,w,h,t[1000][1000]={0},a=0,b=0,d;

bool f[1000][1000]={0};

class Tomato

{

public:

    int x,y,d;

}o;

queue<Tomato> q;

int main()

{

    cin>>w>>h;

    for(int i=0;i<h;i++)

        for(int j=0;j<w;j++)

        {

            cin>>t[i][j];

            if(t[i][j]>=0)a++;

        }

    for(int i=0;i<h;i++)

        for(int j=0;j<w;j++)

            if(t[i][j]>0)

                o.x=i,o.y=j,o.d=0,q.push(o);

    while(!q.empty())

    {

        o=q.front();

        q.pop();

        int i=o.x,j=o.y;

        if(f[i][j])continue;

        f[i][j]=true;

        d=t[i][j],b++;

        if(i-1>=0&&!t[i-1][j])

            o.x=i-1,o.y=j,o.d=d+1,t[i-1][j]=o.d,q.push(o);

        if(i+1<h&&!t[i+1][j])

            o.x=i+1,o.y=j,o.d=d+1,t[i+1][j]=o.d,q.push(o);

        if(j-1>=0&&!t[i][j-1])

            o.x=i,o.y=j-1,o.d=d+1,t[i][j-1]=o.d,q.push(o);

        if(j+1<w&&!t[i][j+1])

            o.x=i,o.y=j+1,o.d=d+1,t[i][j+1]=o.d,q.push(o);

        if(a==b)

        {

            cout<<d-1;

            return 0;

        }

    }

    cout<<"-1";

}