백준 2636 // dfs는 방문처리먼저 해라/ 치즈는 dfs

2636번: 치즈 (acmicpc.net)

2636번: 치즈

000000

001110

000000 일때, (0,0)부터 탐색하면서, 1이면 탐색중지하면(return) 치즈 자동 구현됨.

 

* 의사코드

1. dfs(0,0)

2.if(1) -> v.push, return //1이면 삭제후보에넣고, 탐색종료

 

- 무한루프

dfs(0,0)

3.모두0 -> 프린트(시간, 직전v의크기), 루프탈출

4.아님->삭제후보들=0, 무한루프

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int n,m,t,ret,a[104][104],v[104][140];
vector<pair<int, int>> vv;
int dy[] = {1,0,-1,0};
int dx[] = {0,1,0,-1};

void dfs(int y, int x)
{
    v[y][x] = 1;    //방문처리를 먼저하라.
    if (a[y][x]) { vv.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 || ny >= n || nx < 0 || nx >= m || v[ny][nx]) continue;

        dfs(ny, nx);
    }
    return;
}
int main() {
    ios_base::sync_with_stdio(0);
    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];
        }
    }

    while (true)
    {
        t++;
        vv.clear();
        fill(&v[0][0], &v[0][0] + 104 * 104, 0);

        dfs(0, 0);
        for(pair<int,int> p : vv)
        {
            a[p.first][p.second] = 0;
        }

        ////디버깅
        //for (int i = 0; i < n; ++i)
        //{
        //    for (int j = 0; j < m; ++j)
        //    {
        //        cout<< a[i][j]<<" ";
        //    }
        //    cout << endl;
        //}
        //cout << endl;

        bool fin = true;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (a[i][j] != 0) { fin = false; break;   }
                
            }
        }
        if (fin) { cout << t << "\n" << vv.size(); break; }
        
    }
    
 

   
    return 0;
}