[Inflearn] 토마토(BFS) (c/c++)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

    - 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익음

    - 대각선 방향에 있는 토마토들은 혼자 못 익음

    - 상자의 일부 칸에는 토마토가 들어있지 않을 수 있음

    - M : 가로, N : 세로 (2 <= M,N <= 1,000)

      1 : 익은 토마토, 
      0 : 익지 않은 토마토

      -1 : 토마토가 들어있지 않음

    조건) 인접한 토마토는 왼,오,앞,두 네 방향을 의미

           저장될 떄부터 모든 토마토가 익어있는 상태이면 0을 출력

           모두 익지는 못하는 상황이면 -1 출력

    결과) 창고에 보관된 토마토들이 며칠이 지나면 다 익는지, 그 최소 일수

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

BFS는 이전까지의 거리를 잘 활용해주면 생각보다 간단한 것 같다.

BFS가 좀 익숙해지면 문제만 잘 이해해도 금방 해결할 수 있는(?) 알고리즘 같다.

이번 문제도 똑같다.

문제만 다를 뿐 방식은 같은 것 같다.

상하좌우로 탐색을 하는데,

탐색을 완료하였을 때의 최소결과를 구하는 것이다.

탐색을 하는 과정에서 최소 거리를 구하기 위해

이전 좌표의 거리를 계속해서 더해주면 된다.

아래 그림은 과정의 일부를 그린 것이다.

자세한 설명은 코드로!

#. Code

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 2147000000
#define MIN -2147000000
 
int map[1001][1001], ch[1001][1001];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
 
struct Pos
{
    int x;
    int y;
    Pos(int a, int b)
    {
        x = a;
        y = b;
    }
};
 
queue<Pos> ripe;
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int m, n, i, j, a, rst = MIN;
 
    scanf("%d %d", &m, &n);
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
        {
            scanf("%d", &a);
            map[i][j] = a;
 
            if (a == 1)
                ripe.push(Pos(i, j));
        }
    }
 
    while (!ripe.empty())
    {
        Pos tmp = ripe.front();
        ripe.pop();
 
        for (i = 0; i < 4; i++)
        {
            int xx = tmp.x + dx[i];
            int yy = tmp.y + dy[i];
            
            if (map[xx][yy] == 0 && xx >= 1 && xx <= n && yy >= 1 && yy <= m)
            {
                ripe.push(Pos(xx, yy));
                map[xx][yy] = 1;
                ch[xx][yy] = ch[tmp.x][tmp.y] + 1;
            }
        }
    }
 
    bool flag = false;
 
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
        {
            if (map[i][j] == 0)
            {
                flag = true;
                break;
            }
        }
 
        if (flag)
            break;
    }
 
    if(flag)
        printf("-1\n");
    else
    {
        for (i = 1; i <= n; i++)
        {
            for (j = 1; j <= m; j++)
            {
                if (ch[i][j] > rst)
                    rst = ch[i][j];
            }
        }
 
        printf("%d\n", rst);
    }
 
    return 0;
}

line 10~11) 상하좌우로 탐색하기 위한 좌표

line 13~22) 좌표를 저장하는 구조체

line 40~41) 토마토의 상태를 입력받으면서 토마토가 다 익었을 경우, 해당 좌표를 queue에 push

line 45~62) 주변 토마토를 다 익힐 때까지 반복

line 47~48) 익은 토마토의 좌표를 queue에서 뽑아 저장

line 50~61) 익은 토마토로부터 상하좌우에 안 익은 토마톡가 있는지 탐색

line 52~53) 주변 토마토 좌표 저장

line 55~60) 해당 좌표의 토마토가 익지 않았고 범위 내에 있다면

line 57) 해당 토마토 좌표를 queue에 push

line 58) 해당 토마토를 익힌다 (해당 좌표 1로 수정)

line 59) ch[][]에 이전 토마토 좌표까지의 거리 + 1 을 저장

line 66~79) 모든 좌표를 탐색하면서 안 익은 토마토가 있다면 flag에 표시

line 81~95) 안 익은 토마토가 상자에 있다면 '-1' 출력

line 83~95) 모든 토마토가 익었다면 최소 일수를 출력

    (만일 처음부터 모든 토마토가 익은 상태였다면 최소 일수는 0 출력)

    (0으로 초기화된 상태에서 변화가 없었을 것이므로)

처음에 조건을 잘못 설정해서 헤맸었다..

후아.. 잘 확인하면서 차근차근 해야하는데

왜이렇게 급하게 푸는지.. 

물론 실전처럼 푸는건 좋다만 더 정확하게 푸는 연습을 해보쟈아!!!

#. Other code

#include<stdio.h>
#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, y;
    Loc(int a, int b) {
        x = a;
        y = b;
    }
};
 
queue<Loc> Q;
 
int main() {
    scanf("%d %d", &m, &n);
 
    for(int i = 1; i <= n; i++) {
        for(int 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(int 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(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(tom[i][j] == 0) f = 0;
        }
    }
 
    if(f == 1) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(res<dis[i][j]) res = dis[i][j];
            }
        }
 
        printf("%d\n", res);
    }
    else 
        printf("-1");
    return 0;
}

전체적인 로직은 같았다.

예~~~!

다만 중간중간 실수를 좀 줄여보자..

#. Result

  - Input --------------------------------------------------------

6 4 

0 0 0 0 0 0 

0 0 0 0 0 0 

0 0 0 0 0 0 

0 0 0 0 0 1

------------------------------------------------------------------

  - Output --------------------------------------------------------

8

------------------------------------------------------------------