[백준] 토마토_7576

이 문제를 풀면서 런타임 에러, 컴파일 에러, 메모리 초과, 시간 초과를 모두 볼 수 있었다. 

처음에는 한번 모두 토마토들을 옮기고, 하루 동안 옮긴 토마토들을 배열에 저장해서, 다시 그 토마토들을 익은 토마토 배열에 추가하고... 토마토 배열에 변화가 없으면 그만두는 식으로 풀었다. 그 결과 예제들은 맞았지만 메모리 초과 오류가 났다. 동적 할당도 써봤는데도 틀렸다.  

결국 다른 블로그를 참고해서 풀었다. 전형적인 BFS 문제였는데, days[1000][1000]이라는 배열을 사용하면 간단하게 풀리는 문제였다. 왜 그렇게 이상하게 풀었을까... 공부가 많이 부족해서 그렇다. 

 

이상하게 풀었던 첫 번째 방법 

#include <iostream>
#include <queue>
#include <string.h> 
using namespace std;
 
int m, n; //가로, 세로 
int **arr;
int days;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
queue<pair<int, int>> t;
queue<pair<int, int>> newt;
bool isout(int x, int y) { return x < 0 || y < 0 || x >= m || y >= n;}
 
void tomato() {
    int y = t.front().first;
    int x = t.front().second;
    t.pop();
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (isout(nx, ny)) continue;
        if (arr[ny][nx] != 0) continue;
        newt.push(make_pair(ny, nx));
    }
}
 
void push() {
    int y = newt.front().first;
    int x = newt.front().second;
    newt.pop();
    arr[y][x] = 1;
    t.push(make_pair(y, x));
}
 
bool isremain() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] == 0) return true;
        }
    }
    return false;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> m >> n;
    arr = new int*[n]; 
    for (int i = 0; i < n; ++i) {
        arr[i] = new int[m];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 1) {
                t.push(make_pair(i, j));
            }
        }
    }
 
    while (true) {
        while (!t.empty()) {
            tomato();
        }
        if (newt.empty()) break;
        while (!newt.empty()) {
            push();
        }
        days++;
    }
    if (isremain()) days = -1;
    cout << days;
    for (int i = 0; i < n; i++) {
        delete[] arr[i];
    }
    delete[] arr;
    return 0;
}

 

두 번째 방법 

#include <iostream>
#include <queue>
#include <string.h> 
using namespace std;
 
int m, n; //가로, 세로 
int arr[1000][1000];
int days[1000][1000];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
queue<pair<int, int>> t;
bool isout(int x, int y) { return x < 0 || y < 0 || x >= m || y >= n; }
 
void tomato() {
    int y = t.front().first;
    int x = t.front().second;
    t.pop();
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (isout(nx, ny)) continue;
        if (arr[ny][nx] != 0) continue;
        arr[ny][nx] = 1;
        days[ny][nx] = days[y][x] + 1;
        t.push(make_pair(ny, nx));
    }
}
 
bool isremain() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] == 0) return true;
        }
    }
    return false;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> m >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 1) {
                t.push(make_pair(i, j));
                days[i][j] = 0;
            }
        }
    }
 
    while (!t.empty()) {
        tomato();
    }
    int max_days = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (days[i][j] > max_days) max_days = days[i][j];
        }
    }
    if (isremain()) max_days = -1;
    cout << max_days;
    return 0;
}