89. 토마토 [BFS]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

 

 

풀이 

- 토마토가 다 익는 날짜를 출력하는 문제

- tom 배열에 입력을 받고 1일때마다 큐에 넣는다. (큐에는 Loc 형이 들어가서 (x, y)형태로 저장이 된다.)

- 상하좌우 탐색 하는데 새로구한 좌표에 들어있는 값이 0일때만 경계 안에 있는지 확인 후 큐에 넣어준다.

- 큐에 넣은 후 해당 배열의 값을 1로 만들고(check) 

- dis배열(해당 좌표의 토마토가 익는 날짜수를 갖고 있음)의 카운트를 dis[tmp.x][tmp.y]에 들어있는 값+1로 한다.

- 플래그 f를 사용해 tom배열에서 0이 있는지 검사 => 0이 남아있으면 f=0으로 변경 => -1출력

- f=1이면 모든 토마토가 익었다는 의미 => dis의 최대값을 찾아 res에 넣어준다.

** 이때 초기상태가 모두 익은 토마토라면 dis는 0인 상태로 남아있을 것이고 res는 0이다.(별도 처리 필요 없음)

 

헷갈리는 포인트 정리

1) 뻗어나갈 시작 좌표를 찾는 것

=> 기존 BFS문제에서는 0, 0이라는 시작점이 주어졌다.

=> 해당 문제는 입력 시 1이 들어올때마다 큐에 넣어 시작점을 직접 만들어 줘야 한다.

 

2) dis배열의 사용

=> 자신이 뻗어나온 곳의 dis배열에 +1한 값이 거리가 된다

 

#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
int m, n, tom[1010][1010], res = -2147000000, dis[1010][1010];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

struct Loc
{
    int x;
    int y;
    Loc(int a, int b)
    {
        x = a;
        y = b;
    }
};
queue<Loc> Q;

int main()
{
    int i, j;
    scanf("%d %d", &m, &n); //m열 n행

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
        {
            scanf("%d", &tom[i][j]);
            if (tom[i][j] == 1)
                Q.push(Loc(i, j));
        }
    }

    while (!Q.empty())
    {
        Loc tmp = Q.front();
        Q.pop();
        for (i = 0; i < 4; i++)
        {
            int xx = tmp.x + dx[i];
            int yy = tmp.y + dy[i];
            if (tom[xx][yy] == 0)
            {
                if (xx >= 1 && xx <= n && yy >= 1 && yy <= m)
                {
                    Q.push(Loc(xx, yy));
                    tom[xx][yy] = 1;
                    dis[xx][yy] = dis[tmp.x][tmp.y] + 1;
                }
            }
        }
    }
    int f = 1;
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
        {
            if (tom[i][j] == 0)
                f = 0;
        }
    }
    if (f == 1)
    {
        for (i = 1; i <= n; i++)
        {
            for (j = 1; j <= m; j++)
            {
                if (res < dis[i][j])
                    res = dis[i][j];
            }
        }
        printf("%d\n", res);
    }
    else
        printf("-1");
    return 0;
}