[백준] 2636 치즈

 

링크를 들어가서 문제의 설명을 읽어보고 오자.

www.acmicpc.net/problem/2636

2636번: 치즈

 

이 문제는 bfs를 적절히 활용하면 쉽게 풀리는 문제이다. 공기라고 판단되는 칸 부터 bfs를 실행하여, 한 면이라도 치즈에 닿으면 없애버리면 된다. 이러한 과정을 반복하면서, 치즈가 사라질 때 까지 반복하면 간단히 풀리는 문제이다.

 

bfs 탐색의 시작점은 (0,0) 으로 정했다. 항상 (0,0)은 공기이기 때문이다.

 

이 코드에서는 loc라는 구조체를 선언하여 좌표의 정보를 저장해 두었다.

 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
typedef struct
{
    int x;
    int y;
} loc;
 
int map[101][101];
int visited[101][101];
loc moves[4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int M, N, now_cheeze = 0, last_cheeze = 0, time = 0;
 
int check_cheeze()
{
    int ans = 0;
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            if (map[i][j])
                ans++;
    return (ans);
}
 
void bfs()
{
    queue<loc> q;
    memset(visited, 0, sizeof(visited));
    visited[0][0] = 1;
    q.push({0, 0});
    while (!q.empty())
    {
        loc start = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            loc next = {start.x + moves[i].x, start.y + moves[i].y};
            /* 인덱스 벗어나지 않는지 */
            if (next.x >= 0 && next.x < M && next.y >= 0 && next.y < N)
            {
                /* 방문하지 않은 곳이면 */
                if (!visited[next.x][next.y])
                {
                    visited[next.x][next.y] = 1;
                    /* 방문한 곳이 치즈라면? */
                    if (map[next.x][next.y] == 1)
                    {
                        map[next.x][next.y] = 0;
                        now_cheeze--;
                    }
                    /* 방문한 곳이 치즈가 아니라면? */
                    else
                        q.push({next.x, next.y});
                }
            }
        }
    }
    time++;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> M >> N;
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == 1)
                now_cheeze++;
        }
    }
    while (now_cheeze)
    {
        last_cheeze = now_cheeze;
        bfs();
    }
    cout << time << "\n";
    cout << last_cheeze;
    return (0);
}

 

애초에 입력받는 경우의 수가 매우 적어서, C++로 풀이하면 0ms가 나온다. 이거보다 비슷하지만 약간 어려운 문제가 있다. 시간이 나면 아래 문제도 같이 풀어보자.

www.acmicpc.net/problem/2638 

2638번: 치즈