[BOJ] 7576 토마토

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

7576번: 토마토

 

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

bfs

 

---------------------------------------------------풀이----------------------------------------------------

 

큰 구조는 다음과 같다.

1. 모든 토마토가 익었는지 is_complete()을 통해 체크한다. map[][]에 0이 있으면 false, 아니면 true이다.

2. 모든 토마토가 익은게 아니면 queue가 비었는지 체크한다. queue가 비었으면 익힐 수 없는 토마토가 존재하는 것이므로 종료한다.

3. queue에 담긴 새로 익은, 이웃한 네 방향을 조사해야 할 토마토의 이웃한 토마토를 조사하기 위해 queue에 담는다.

 

여기서 queue를 사용한 이유는, 최대 1000x1000을 매번 조사해야하는 시간을 줄이기 위해서이다.

즉, 맨 처음 익은 토마토(1)들에서 출발해 그 토마토와 이웃한, 새로 익은 토마토를 큐에 넣고,

다시 그 익은 토마토들과 이웃한 새로 익은 토마토를 큐에 넣고, ...

이 작업을 더 이상 익을 수 있는 토마토가 없거나(return -1) 모든 토마토가 익은 경우(return 걸린 시간)까지 반복한다.

그럼 경계값에 대해서만 조사를 계속할 수 있을 것이다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>

using namespace std;

int N, M;
int map[1001][1001] = {0, };
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
bool visited[1001][1001] = {false, };
queue<pair<int,int> > q;

// 모든 토마토가 익은 경우
bool is_complete(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(map[i][j] == 0){
                return false;
            }
        }
    }
    return true;
}

void print_all(){
    printf("\n");
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            printf("%3d ", map[i][j]);
        }
        printf("\n");
    }
}

int solution(){
    pair<int,int> cur;
    int ans = 0;
    while(!is_complete()){
        //print_all();
        ans++;
        queue<pair<int,int> > tmpq;
        if(q.empty()){
            ans = -1;
            break;
        }
        while(!q.empty()){
            cur = q.front();
            q.pop();
            int nx, ny;
            for(int i = 0; i < 4; i++){
                nx = cur.first + dx[i];
                ny = cur.second + dy[i];
                if(nx < 0 || nx >= N || ny < 0 || ny >= M 
                    || visited[nx][ny] || map[nx][ny] != 0){
                    continue;
                }
                tmpq.push(make_pair(nx, ny));
                map[nx][ny] = 1;
                visited[nx][ny] = true;
            }
        }
        q = tmpq;
    }
    return ans;
}

int main(void){
    FASTIO;
    cin >> M >> N;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> map[i][j];
            if(map[i][j] == 1){
                q.push(make_pair(i, j));
                visited[i][j] = true;
            }
        }
    }
    cout << solution() << "\n";
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

세로를 N, 가로를 M이라 했을 때, 입력이 M N 순서로 들어옴에 주의해야 한다.

알고리즘 상에 큰 문제가 없어보이는데 원하는대로 동작하지 않아서

print_all()로 찍어봤더니 N과 M이 반대로 되어있다는 것을 눈치챘다!