백준 2636 치즈

빡 구현 문제를 잡았다. 2D BFS 문제에서 풀듯이 접근해보자 싶었고, 그 접근이 맞았다.

맵 입력을 받고, 테두리를 돌면서 BFS로 탐색을 한다. 상하좌우 탐색을 하면서 빈 공간을 만나면 그 위치도 큐에 넣는다. 만약 치즈를 만나면 그 부분은 공기와 접촉한 부분이므로 표시를 해둔다. 탐색을 하면서 꼭 visited[][] 배열을 채워주자. 테두리 탐색할때나, 큐 안에서 탐색할 때 visited[][] 로 이미 방문한 곳 처리를 하지 않으면 무한루프가 돌거나 연산 속도가 너무 느려질 가능성이 높다.

 

한번 모든 테두리에서 BFS 탐색으로 접촉면을 표시해준 다음, 전체 위치를 돌면서 녹는 부분을 제거해주고, 치즈 자리수를 세줬다. 치즈 자리수가 0이 되면 모든 치즈가 없어진 것이므로 탐색 종료! 가장 마지막으로 계산했던 치즈 자리수와 반복 횟수를 출력해주면 된다!

---

#include <queue>
#include <vector>
#include <iostream>

int main()
{
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
    int n, m;
    int cheese = 0;
    int hour = 0;
    std::cin >> n >> m;

    std::vector<std::vector<int>> map(n, std::vector<int>(m, 0));

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            std::cin >> map[i][j];
            if (map[i][j] == 1)
                cheese++;
        }
    }
     while (1)
    {
        hour++;
        std::vector<std::vector<int>> visited(n, std::vector<int>(m, 0));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if ((i == 0 || i == n-1 || j ==0 || j == m-1) && !visited[i][j])
                {
                    std::queue<int> q;
                    q.push(i * m + j);
                    while (!q.empty())
                    {
                        int cur_x = q.front() % m;
                        int cur_y = q.front() / m;
                        q.pop();
                        if (visited[cur_y][cur_x])
                            continue;
                        visited[cur_y][cur_x] = 1;
                        for (int k = 0; k < 4; k++)
                        {
                            int nx = cur_x + dx[k];
                            int ny = cur_y + dy[k];

                            if (nx >= 0 && nx < m && ny >= 0 && ny < n)
                            {
                                if (map[ny][nx])
                                    map[ny][nx] = 2;
                                else
                                    q.push(ny * m + nx);
                            }
                        }
                    }
                }
                else
                    continue;
            }
        }
        int cheese_cnt = 0;
        // std::cout << '\n';
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                // std::cout << map[i][j] << " ";
                if (map[i][j] == 2)
                    map[i][j] = 0;
                if (map[i][j] == 1)
                    cheese_cnt++;
            }
            // std::cout << '\n';
        }

        if (cheese_cnt == 0)
            break;
        cheese = cheese_cnt;
    }
    std::cout << hour << '\n' << cheese;
}

 

정신이 없어서 좀 쉬운 문제를 잡아봤다. 처음 접근한 방향이 맞아서 기분이 좋다. 중간에 인덱스 처리로 OOB 런타임 에러가 떴지만, 금방 찾아서 다행이다.

 

오늘도 평온한 하루가 되길. 슨민.