2636번

2636번 - 치즈

이번 문제는 DFS를 이용해서 문제를 풀 수 있었다.

기본적인 아이디어는 치즈가 아닌 부분을 DFS로 탐색하면서, 치즈가 아닌 부분의 근처에 있는 치즈만을 2로 변경시켜준다.

DFS가 종료된 이후에는, 체크된 2의 값들을 카운트하고, 다시 0으로(치즈가 사라졌으므로) 값을 변경시킨다.

이런식으로 2로 변경된 치즈가 없을 때까지 while문을 진행하면 시간값과 치즈갯수를 구할 수 있다.

<정답 코드>

#include<iostream>
 
using namespace std;
 
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
 
int map[101][101];
bool visited[101][101];
int n, m;
void init()
{
    //dfs를 다시 진행하기 위해 visited 배열 초기화
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            visited[i][j] = false;
}
int check()
{
    //2로 값이 변경된 없어진 치즈들을 카운트하고, 0으로 변경
    int sum = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (map[i][j] == 2)
            {
                sum++;
                map[i][j] = 0;
            }
 
    return sum;
}
 
//map 값이 0인 지점들을 dfs
void search(int x,int y)
{
    visited[x][y] = true;
 
    for (int d = 0; d < 4; d++)
    {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (nx >= 0 && ny >= 0 && nx < n && ny < m && map[nx][ny] == 0 && !visited[nx][ny])
            search(nx, ny);
 
        
        //dfs를 하면서 치즈와 인접한 부분은 2로 변경
        if (map[nx][ny] == 1)
            map[nx][ny] = 2;
    }
 
}
int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> map[i][j];
 
 
    int time = 0;
    int ans;
    while (true) {
        init();                    //visited 값 초기화
        search(0,0);            //dfs진행
        int tmp = check();        //사라진 치즈 확인 및 0으로 값 변경
        if (tmp == 0)
            break;                //사라진 치즈가 0개 이면, 치즈가 모두 사라졌으므로 break
        ans = tmp;
        time++;
    }
 
    cout << time << endl;
    cout << ans << endl;
 
    return 0;
}