#2573번 빙산 (C++)

링크 : www.acmicpc.net/status?user_id=shuhu_01&problem_id=2573&from_mine=1

채점 현황

문제의 풀이는 다음과 같다. 

(1) 배열 arr에 값을 입력한다. 

(2) 배열 arr의 각 위치에 위 / 아래 / 좌 / 우의 값이 0인 갯수만큼 마이너스 한 값을 배열 v에 옮겨준다. (melt 함수 참고)

* 배열을 이중으로 만들지 않고 순차적으로 하나하나 값을 계산해주면 다음과 같은 실수를 겪게된다. 

	1 -> 0	3
	3	2

주변의 '0'의 값만큼 제외해주는 계산으로 1의 값이 0으로 되고, 그대로 다음 배열의 값으로 넘어갈경우

		0
	1 -> 0	3 -> 0	0
	3	2

3의 값이 0으로 변경되어버린다. 원래 옳바른 계산은 위쪽 / 오른쪽의 0의 갯수 2개만큼 제외하여 1이 되어야한다.

(4) 이때 v배열의 값을 temp에 누적시켜준다. 이는 빙하가 모두 녹았음에도 2개 이상으로 빙산이 분리되지 않음을 구분하기 위함이다.

(5) 분리된 빙하의 지역 갯수를 세는 for문을 진행한다. 이때 계산되었던 값 v배열은 arr로 재복사해준다. (track 함수 참고)

(6) 분리된 빙하의 값 total이 1개를 초과하면 걸린 시간 year을 출력하고 종료한다. 

(7) 만약 분리된 빙하의 값이 1개를 초과하지 못하고, 모든 빙하가 녹아버렸을 경우 (temp ==0) 결과를 출력하고 종료한다.

(8) 마지막으로 방문 여부를 확인하기 위한 ch배열(bool)과 빙산의 갯수 total은 초기화 해준다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int arr[302][302] = {0,}, v[302][302] = {0,}, year = 0, total = 0, temp = 0, n = 0, m = 0;
bool ch[302][302] = {false,};
int my[4] = {1,0,-1,0};
int mx[4] = {0,1,0,-1};

int melt(int y, int x){
    int cnt = 0;
    for(int i=0; i<4; i++){
        int ny = y + my[i];
        int nx = x + mx[i];
        if(arr[ny][nx]==0) cnt++;
    }
    return cnt;
}

void track(int y, int x){
    for(int i=0; i<4; i++){
        int ny = y + my[i];
        int nx = x + mx[i];
        if(ny>=1&&ny<=n&&nx>=1&&nx<=m){
            if(v[ny][nx]!=0&&!ch[ny][nx]){
                ch[ny][nx] = true;
                track(ny,nx);
            }
        }
    }
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m; // n = y, m = x;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> arr[i][j];
        }
    }
    while(true){
        temp = 0;
        ++year;
        for(int i=2; i<=n-1; i++){
            for(int j=2; j<=m-1; j++){
                if(arr[i][j]>0){
                    v[i][j] = arr[i][j] - melt(i,j);
                    if(v[i][j]<0) v[i][j] = 0;
                }
                temp+=v[i][j];
            }
        }
        for(int i=2; i<=n-1; i++){
            for(int j=2; j<=m-1; j++){
                arr[i][j] = v[i][j];
                if(v[i][j]!=0&&!ch[i][j]){
                    total++;
                    ch[i][j] = true;
                    track(i,j);
                }
            }
        }
        if(total>1){
            cout << year << "\n";
            exit(0);
        }
        if(temp==0){
            cout << temp << "\n";
            exit(0);
        }
        memset(ch,false,sizeof(ch));
        total = 0;
    }
    return 0;
}

배열을 복사할 생각을 하지 않고 순차적으로 계산해주는것만 생각하여 결국 오류를 발생시켰다.

이 문제는 분명 BFS로도 풀 수 있을 것 같다. #7576번 토마토와 비슷하게 풀 수 있을것 같은데, 근 시일내로 다시 재도전 해야겠다.