[백준 2636] 치즈

문제유형:

그래프 탐색 dfs/bfs 

복기

outDfs에서 else return문을 넣어주지 않았다. 
해당 return문이 없으면 visited 처리가 되지 않아 계속 무한 탐색하게 된다. 

#include <bits/stdc++.h>
using namespace std; 
typedef pair<int,int> pp; 

int cnt=0;
int m,n,rnd=0; 
int prevEdgesCnt; 
int a[104][104];
int visited[104][104]; 
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0}; 
vector<pp> currMeltedCheese; 

bool outOfBound(int y, int x){
    return (y < 0 || x < 0 || x >= m || y >= n); 
} 

//outDfs
void outDfs(int y, int x){
    if( a[y][x] == 0 ) visited[y][x] = 1;//outair
    else return; //else return이 없으면 해당 노드 visited 처리가 안 돼서 무한 방문문
    
    for(int i=0; i<4; i++){
        int ny = y + dy[i]; 
        int nx = x + dx[i];
        if( outOfBound(ny,nx) || visited[ny][nx] ) continue; 
        outDfs(ny,nx); 
    }
}

//// isMeltable
bool isMeltable(int y, int x){
    int ny,nx; 
    for(int i=0; i<4; i++){
        ny = y + dy[i]; 
        nx = x + dx[i]; 
        if( outOfBound( ny,nx ) ) continue; 
        if( visited[ny][nx] ) return true; 
    }
    return false; 
}

void melt(){
    for(int i=1; i<n; i++){
        for(int j=1; j<m; j++){//현재 방문 중인 노드가 1이고 외부 공기와 인접해 있는 경우
            if(a[i][j] == 1){ //치즈인 경우 녹는 치즈인지 확인
                if( isMeltable(i,j) ){ //melt
                    a[i][j] = 0; 
                    currMeltedCheese.push_back( {i,j} ); 
                }
            }
        }
    }
}

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

// 초기화 
void init(){
    fill(&visited[0][0], &visited[0][0] + 104 * 104, 0);
    currMeltedCheese.clear(); 
}

void solve(){
    input();
    while(true) {
        init();
        outDfs(0,0);// dfs 
        melt(); 

        // when all melted     
        if( currMeltedCheese.size() == 0 ){
            cout << rnd << "\n"; 
            cout << prevEdgesCnt; 
            break; 
        }
        
        rnd++;
        prevEdgesCnt = currMeltedCheese.size(); 
    }
}

int main() {
    solve();
    return 0;
}