백준 2636 - 치즈(C++)

문제 링크입니다 https://www.acmicpc.net/problem/2636

2636번: 치즈

 

문제 조건

출력 예시

 

문제 접근 방법

1. 현재 남아 있는 치즈의 갯수를 확인한다.

2. 치즈가 남아있을 경우, 공기를 BFS를 통해서 탐색한다.

3. 공기와 접촉되어 있는 치즈를 녹은 상태로 만들어준다.

4. 치즈를 녹여준뒤, 다시 반복한다.

 

 

문제 접근 방법 - 1번

bool get_cheese() {
    int cnt = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (map[i][j] == 1) {
                cnt++;
            }
        }
    }
    if (cnt > 0) {
        remain.push_back(cnt);
        return false;
    }
    else return true;
}

map[][]배열을 확인해서 남아있는 치즈가 있는지 확인을 합니다.

1. 남아있는 치즈가 없을 경우에는 탐색을 더이상 할 필요가 없으니, true를 return 했습니다.

2. 남아있는 치즈가 있을 경우에는 남아있는 치즈의 갯수를 저장했습니다. -> 마지막으로 남은 치즈를 출력할때 사용 

 

 

문제 접근 방법 - 2번

void melt_cheese(int x, int y) {
    cheese.push(make_pair(x, y));
    while (!cheese.empty()) {
        int x1 = cheese.front().first;
        int y1 = cheese.front().second;
        cheese.pop();
        find_cheese(x1, y1);
        for (int i = 0; i < 4; i++) {
            int xx = x1 + dx[i];
            int yy = y1 + dy[i];
            if (xx >= 1 && yy >= 1 && xx <= N && yy <= M) {
                if (map[xx][yy] == 0 && check_air[xx][yy] == 0) {
                    check_air[xx][yy] = 1;
                    cheese.push(make_pair(xx, yy));
                }
            }
        }
    }   
}

주어진 map에서는 가장자리가 항상 공기였습니다. 그렇다면 가장자리 공기에서 시작해서 치즈를 둘러싼 공기들을 탐색한다면, 녹을 수 있는 치즈들을 확인할 수 있습니다.

공기들을 찾으면서, 동시에 해당 좌표에서 녹을 수 있는 치즈를 같이 찾았습니다.

 

 

문제 접근 방법 - 3번

void find_cheese(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (map[xx][yy] == 1) {
            check_cheese[xx][yy] = 1;
        }
    }
}

void get_rid_of() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (check_cheese[i][j] == 1) {
                map[i][j] = 0;
            }
        }
    }
}

check_cheese[][]에 1이 저장되었다는 것은, 공기와 접촉해 다음에 녹을 치즈라는 의미입니다. 이들을 없애줬습니다.

 

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;

int N, M;
int answer;
int map[101][101];
int check_cheese[101][101];
int check_air[101][101];
queue<pair<int, int>> cheese;
vector<int> remain;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

bool get_cheese() {
    int cnt = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (map[i][j] == 1) {
                cnt++;
            }
        }
    }
    if (cnt > 0) {
        remain.push_back(cnt);
        return false;
    }
    else return true;
}

void find_cheese(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (map[xx][yy] == 1) {
            check_cheese[xx][yy] = 1;
        }
    }
}

void melt_cheese(int x, int y) {
    cheese.push(make_pair(x, y));
    while (!cheese.empty()) {
        int x1 = cheese.front().first;
        int y1 = cheese.front().second;
        cheese.pop();
        find_cheese(x1, y1);
        for (int i = 0; i < 4; i++) {
            int xx = x1 + dx[i];
            int yy = y1 + dy[i];
            if (xx >= 1 && yy >= 1 && xx <= N && yy <= M) {
                if (map[xx][yy] == 0 && check_air[xx][yy] == 0) {
                    check_air[xx][yy] = 1;
                    cheese.push(make_pair(xx, yy));
                }
            }
        }
    }   
}

void get_rid_of() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (check_cheese[i][j] == 1) {
                map[i][j] = 0;
            }
        }
    }
}

void solve() {
    while (1) {
        memset(check_cheese, 0, sizeof(check_cheese));
        memset(check_air, 0, sizeof(check_air));
        if (get_cheese()) break;
        melt_cheese(1,1);
        get_rid_of();
        answer++;
    }
    cout << answer << "\n";
    cout << remain[remain.size() - 1];
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> map[i][j];
        }
    }
    solve();
    return 0;
}

 

질문 및 조언 댓글 남겨주세요!