DFS를 이용해 테두리를 제거하는 문제이다.

(1) 가장 바깥쪽은 전부 치즈가 존재할 수 없는 영역이라는 조건은 왜 주어졌을까 ?

이 문제에서 특이한점은 가장 바깥쪽은 전부 치즈가 존재할 수 없는 영역이라는 것이다.
왜 이런 조건을 주었을까? 이 조건 덕분에 우리는 어디서 DFS를 시작해야할지 찾지 않아도된다. 이조건 덕분에 가장 가쪽 영역 어디에서나 DFS를 호출하면 자동으로 연결된 컴포넌트를 순회하기때문이다.

-> (0,0)에서 시작하여 DFS를 수행하면 치즈 바깥쪽을 순회할 수 있다.

(2) DFS의 본질은 연결된 컴포넌트의 순회이다.

DFS는 재귀적으로 연결된 컴포넌트를 순회하는 로직이다. 우리는 DFS를 통해 치즈 바깥쪽 부분을 순회할 수 있다. 이때 4방향 탐색을 할텐데, 필연적으로 치즈의 테두리(치즈가 공기와 접하는 부분)를 방문하게된다. 그렇다면 테두리의 좌표만 따로 뽑아낼수 있지 않을까?
-> 각 방문마다 방문 처리후에 a[][]가 1이라면 치즈의 테두리이므로 vector에 넣어주자

1. 풀이

#include <bits/stdc++.h>

using namespace std;

int n,m,ret,cnt;
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 >= n || nx >= m || visited[ny][nx]) continue;
        dfs(ny,nx); 
    }    
}

bool is_1_exist() {
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(a[i][j]==1) return true;
        }
    }
    return false;
}
int main() {
    cin >> n >> m;
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cin >> a[i][j];
        }
    }
    while(is_1_exist()) {
        fill(&visited[0][0],&visited[0][0]+104*104, 0);
        dfs(0,0);
        for(pair<int,int> p: v) {
            a[p.first][p.second] = 0;
        }
        cnt = v.size();
        ret++;
        v.clear();
    }
    cout << ret << '\n' << cnt;
    return 0;
}

2. 오답노트

(1) DFS의 본질은 그래프의 순회이다

DFS는 연결된 컴포넌트를 순회한다. 이를 잘 생각해보면, 당연히 그 과정에서 치즈이 바깥 테두리를 방문하므로, 치즈 바깥 테두리의 좌표를 알아낼 수 있다.

이렇듯 DFS문제인데 단순 DFS로 안풀리는 문제는 꼭 DFS과정을 시뮬레이션해보며, 그 DFS 과정에서 내가 찾고자하는 노드가 방문이 되는지를 생각해보는 것이 중요하다.

만약 DFS과정에서 방문이 이뤄진다면, DFS함수를 조금만 수정하면 문제를 풀 수 있다.