[백준] 치즈 2638번 (c++)

출처 : 2638번: 치즈 (acmicpc.net)

2638번: 치즈

풀이 방법

dfs로 풀이하였다

모눈종이의 가장자리가 비어있다고 가정했으므로 치즈 밖의 공기들은 다 연결되어있다.

치즈 밖의 공기는 다 연결되어있으므로 dfs(0,0)으로 하면 다 탐색할 수 있다.

탐색 중 보드 값이 1인 치즈를 만나면 +1을 해주어 보드 값을 2로 만들어 주고 

탐색중 보드 값이 2인 치즈를 만나면 mel_cheese벡터에 추가해 주고 visited 값을 1로 바꾸어 주어 다시

방문하지 않게 한다

이 과정이 끝나면 del_cheese 함수를 호출하여 mel_cheese벡터에 포함되어있는 치즈를 녹여 준 후

전체 visited 값을 -1로 초기화하고 mel_cheese 벡터를 비워주고 new_board를 통해 녹지 않았지만 

board가 2가 된 치즈를 1로 초기화시켜 다음 dfs를 수행하기 위해 자료를 준비해준다.

 

종료 조건은 dfs를 수행 후 mel_cheese 벡터의 사이즈가 0이 되면 더 이상 녹일 치즈가 없다는 뜻이므로

while문을 탈출하고 time을 출력한다.

//치즈
#include <bits/stdc++.h>
using namespace std ;

int board[101][101];
int n, m, time_ = 0;
int visited[101][101];
vector<pair<int, int>> mel_cheese;
bool empty_board = false;
int num_cheese;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

void dfs(int y, int x) {
        if (visited[y][x] == 1) return ;
        visited[y][x] = 1;
        for (int i = 0;i < 4;i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (visited[ny][nx] == -1 && ny >= 0 && ny < n && nx >= 0 && nx < m) {
                if (board[ny][nx] == 1) {
                    board[ny][nx]++;
                }
                else if (board[ny][nx] == 2) {
                    mel_cheese.push_back(make_pair(ny, nx));
                    cout << ny <<" " <<nx <<endl;
                    board[ny][nx] = 1;
                    visited[ny][nx] = 1;
                }
                else {
                    dfs(ny, nx);
                }
            }
        }
        return ;
}

void del_cheese() {
    num_cheese = mel_cheese.size();
    for (int i = 0;i < mel_cheese.size();i++) {
        int yy = mel_cheese[i].first;
        int xx = mel_cheese[i].second;
        board[yy][xx] = 0;
    }
    return ;
}
void new_board() {
    for (int i = 0;i < n;i++) {
        for (int k = 0;k < m;k++) {
            if (board[i][k] == 2) {
                board[i][k] = 1;
            }
        }
    }
}
int main () {
    cin >> n >> m;
    memset(visited, -1, sizeof(visited));
    for (int i = 0;i < n;i++) {
        for (int k = 0;k < m;k++) {
            cin >> board[i][k];
        }
    }
    while(empty_board != true) {
            dfs(0, 0);
            if (mel_cheese.size() == 0) {
                empty_board = true;
                cout << time_ << endl;
            }
            time_++;
            del_cheese();
            memset(visited, -1, sizeof(visited));
            mel_cheese.clear();
            new_board();
    }
    return 0;
}