본인 풀이

#include<bits/stdc++.h>
using namespace std;
int n, m;
int ret = 0;
int cheese = 0;
int visited[100][100], a[100][100];
map<pair<int, int>, bool> mp;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

int dfs(int y, int x){
    int result = 1;
    visited[y][x] = 1;

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

        // 가이드라인 계산을 어떻게할지?
        if(a[y][x] && !a[ny][nx]){
            mp[{y, x}] = true;
        }

        if(visited[ny][nx]){
            continue;
        }

        // 분기처리를 여기서하면 공기 자체였던곳도 카운트해버림
        if(ny < 0 || nx < 0 || ny >= m || nx >= n || !a[ny][nx]){
            continue;
        }
        result += dfs(ny, nx);
    }

    return result;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int cnt = 0;
    int last_ret = 0;

    cin >> m >> n;
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            cin >> a[i][j];
            if(a[i][j] == 1){
                cnt++;
            }
        }
    }

    while(cnt > 0){
        ret++;
        last_ret = 0;
        mp.clear();
        memset(visited, 0, sizeof(visited));
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if(!visited[i][j] && a[i][j]){
                    last_ret += dfs(i, j);
                }
            }
        }
        // 공기에 닿은곳 치즈 녹이기
        for (auto it : mp)
        {
            a[it.first.first][it.first.second] = 0;
            cnt--;
        }
    }
    cout << ret << "\n";
    cout << last_ret << "\n";
    return 0;
}

1. 실패했음
2. 치즈영역을 DFS하여 공기와 맞닿은 곳을 녹이도록 map 자료구조를 통해 로직을 설계했는데, 치즈로 둘러쌓인 공기 영역에 대해서는 처리하지 못했음

모범 답안

#include<bits/stdc++.h>
using namespace std;
int m, n;
int a[104][104];
int visited[104][104];
vector<pair<int, int>> v;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

void dfs(int y, int x){
    visited[y][x] = 1;
    if(a[y][x]){
        v.push_back({y, x});
        return;
    }

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

        if (ny < 0 || nx < 0 || ny >= m || nx >= n || visited[ny][nx]){
            continue;
        }
        dfs(ny, nx);
    }
}

int main(){
    cin >> m >> n;
    int ret = 0;
    int ret2 = 0;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++){
            cin >> a[i][j];
        }
    }

    while(true){
        ret++;
        memset(visited, 0, sizeof(visited));
        v.clear();
        dfs(0, 0);
        for(auto it: v){
            a[it.first][it.second] = 0;
        }
        ret2 = v.size();

        bool flag = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++){
                if(a[i][j]!=0){
                    flag = 1;
                }
            }
        }
        if(!flag){
            break;
        }
    }
    cout << ret << "\n" << ret2 << "\n";
    return 0;
}

1. DFS를 꼭 모든 좌표에 대해서 순회해야하는 고정관념을 깨자
2. 바깥쪽 공기 영역은 반드시 한개의 연결된 컴포넌트로 구성되어 있으므로, 이에 대한 DFS순회 한번으로 공기와 접한 치즈들을 알아낼 수 있다.
3. 공기와 접한 치즈들의 좌표를 벡터에 저장하여 녹이자.
4. 공기와 접한 벡터 사이즈가 최종 녹이기 전 남은 치즈의 갯수가 된다.

복습 (7/17)

성공

#include<bits/stdc++.h>
using namespace std;
int n, m, cheese = 0;
int a[104][104];
int visited[104][104];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

void dfs(int y, int x){
    visited[y][x] = 1;
    // 치즈 녹이고 순회종료
    if(a[y][x] == 1){
        cheese--;
        a[y][x] = 0;
        return;
    }

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

        if(ny < 0 || nx < 0 || ny >= n || nx >= m){
            continue;
        }
        if(visited[ny][nx]){
            continue;
        }

        dfs(ny, nx);
    }
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> a[i][j];
            if(a[i][j] == 1){
                cheese++;
            }
        }
    }

    int cnt = 0;
    int ret = 0;
    while (cheese > 0){
        memset(visited, 0, sizeof(visited));
        ret = cheese;
        dfs(0, 0);
        cnt++;
    }

    cout << cnt << "\n";
    cout << ret << "\n";

    return 0;
}

1. 치즈 녹이고 순회를 종료하는 타이밍을 이해하게 됨
2. DFS 겉돌기 한번만 진행하기
3. continue조건에 visited도 꼭 삽입하기