백준, BOJ, 2573번, 빙산 : C++ [CPP]

 

어려웠다.

조건이 많았기 때문이다.

 

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

 

---

 

#맞는 풀이

#include <iostream>
#include <algorithm>

#define X first
#define Y second

using namespace std;

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

int R, C;

int curMap[300][300];
int nextMap[300][300];
int year = 0;


int visited[300][300]; //dfs를 위함

void melting(int x, int y) {
    int cnt = 0; //주변 바다의 칸 

    for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        //범위
        if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
        //현재 바다에 접해있는 칸이 있으면
        if(curMap[nx][ny] == 0){
            cnt++; //바다 해당 개수 ++
        }
    }

    //해당 바다가 접한 수 -> nextMap 업데이트
    nextMap[x][y] = max(0,curMap[x][y] - cnt); //0보다 작아지지 않음 (clamp)
}

//nextMap에서의 DFS체크
void dfs(int x, int y) {
    visited[x][y] = 1;


    for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        //범위
        if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
        //빙산이 아닌 바다거나, 이미 방문했으면 pass
        if (visited[nx][ny] != 0 || nextMap[nx][ny] == 0)continue;

        //visited[x][y] = 1; -> 방문을 여기서 처리하니까 문제가됨????????

        dfs(nx, ny);


    }

}

//next Map에서 빙산이 몇덩이인지 체크.
int chunkCheck() {
    int cnt = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            //방문하지 않았고 빙산일 경우 시작노드
            if (nextMap[i][j] != 0 && visited[i][j] == 0) {
                cnt++;
                //visited[i][j] = 1; -> 방문을 여기서 처리하니까 문제가됨??????????
                dfs(i, j);
            }
            //2덩이 이상이면 바로 종료
            if (cnt >= 2) {
                return cnt;
            }
        }
    }
    //2덩이 미만이면 1덩이인지 아예 빙산이 사라졌는지 판단.
    return cnt;
}


int main() {
    cin >> R >> C;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> curMap[i][j]; // 입력을 차례대로 현재 맵에 집어넣음
            nextMap[i][j] = curMap[i][j]; // NextMap은 처음에 curMap으로 초기화함 (체크를위해)
        }
    }

    bool isDone = false; //빙산이 2조각 이상인지

    //처음에 이미 2조각인지 조사.
    int temp = chunkCheck();
    if (temp >= 2) {
        isDone = true;
       // cout << "true";
    }
    //빙산이 하나도 없으면
    else if(temp == 0){
        isDone = true;
        year = 0;
    }
    

    // chunkCheck에서 쓴 visited 초기화
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            visited[i][j] = 0; 
        }
    }


    //빙산이 2조각 이상이 아니면
    while (!isDone) {

        //현재 맵으로 nextMap 업데이트
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (curMap[i][j] != 0) {
                    melting(i, j);
                }
            }
        }

        year++;

        //nextMap이 2조각인지 조사.
        int temp = chunkCheck();
        if (temp >= 2) {
            break;
        }
        else if(temp == 0){
            isDone = true;
            //한 번에 다녹으면 0
            year = 0;
        }

        //아니면 nextMap을 curMap으로 업데이트
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                curMap[i][j] = nextMap[i][j];
                visited[i][j] = 0; // 다시 방문하기 위해 visited 초기화
            }
        }

    }

    cout << year;

}

 

 

1. nextMap과 curMap을 따로 저장해야함

-> 같이할 경우 curMap 에서 녹아서 생긴 바다를 중복으로 체크하는 경우 생김

 

2. 2조각 이상이거나 한 번에 다 녹았을 경우까지 계속 반복해야함.

-> 예외처리

 

 

노드탐색 중에서도

단계 별로 노드들을 복사해서 해야해서 까다로웠다.