[백준/C++] 2636번: 치즈

로봇청소기도 어려웠는데 이 문제도 어려웠다. 초등부문제라니 정말..^^

풀이과정을 머릿속으로 떠올려보니,

 

1) while문을 돌리는데 종료조건은 

2) initial함수: visit배열은 사이클을 돌 때마다 초기화해줘야 한다.

3) outAir함수: 외부공기와 내부공기를 구분해줘야 하는데 이는 dfs를 0,0칸에서 돌려주면 자동으로 구분된다. 그 이유는 치즈에 맞닿아있으면 dfs가 탐색을 못하기 때문에 자동으로 못들어간다. 외부공기를 새로운 visit배열에 표시를 해주었다.

4) melt함수: 모든 위치를 돌며 그 위치의 동서남북에서 visit배열의 표시가 하나라도 있으면 외부공기와 맞닿은 부분이 된다. 그래서 이부분을 녹이고, 기존 치즈 갯수에서 1을 빼준다.

 

5) 출력 만들기: 시간같은 경우 while문 한 cycle을 돌 때마다 1씩 증가시켰고 치즈갯수는 사이클돌면서 업데이트를 해주는데 종료조건을 만날 때는 업데이트가 되지 않아야하기 때문에 종료조건 이후 업데이트 시켰다.

 

#include<iostream>
#include<cstring>
using namespace std;

int N, M;
int nCheeze = 0;
int map[101][101] = { 0 };
int visit[101][101] = { 0 };
int dx[] = { 1,0,0,-1 };
int dy[] = { 0,1,-1,0 };

void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
            if (map[i][j] == 1) nCheeze++;
        }
    }
}
void init() {
    memset(visit, 0, sizeof(visit));
}

void outAir(int x, int y) {
    if (visit[x][y] == 0)visit[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
        if (map[nx][ny] == 0 && visit[nx][ny] == 0) outAir(nx, ny);
    }
    return;
}
void melt() {
    //테두리는 탐색할 필요가 음슴
    for (int i = 1; i < N - 1; i++) {
        for (int j = 1; j < M - 1; j++) {

            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
                if (visit[nx][ny] == 1) {
                    if (map[i][j] == 1) {
                        map[i][j] = 0;
                        nCheeze--;
                        break;
                    }
                }
            }

        }
    }
}


int main() {

    int time = 0;
    int final_cheeze = 0;


    input();
    while (1) {

        final_cheeze = nCheeze;
        init();
        outAir(0, 0);
        melt();
        time++;
        if (nCheeze == 0)break;
      
    }

    cout << time << "\n";
    cout << final_cheeze;

}