백준 16724번

오늘 풀어본 문제는 백준의 16724번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

피리 부는 사나이 성우는 오늘도 피리를 분다.

성우가 피리를 불 때면 영과일 회원들은 자기도 모르게 성우가 정해놓은 방향대로 움직이기 시작한다. 성우가 정해놓은 방향은 총 $4$ 가지로 U, D, L, R이고 각각 위, 아래, 왼쪽, 오른쪽으로 이동하게 한다.

이를 지켜보던 재훈이는 더 이상 움직이기 힘들어하는 영과일 회원들을 지키기 위해 특정 지점에 ‘SAFE ZONE’ 이라는 최첨단 방음 시설을 만들어 회원들이 성우의 피리 소리를 듣지 못하게 하려고 한다. 하지만 예산이 넉넉하지 않은 재훈이는 성우가 설정해 놓은 방향을 분석해서 최소 개수의 ‘SAFE ZONE’을 만들려 한다.

성우가 설정한 방향 지도가 주어졌을 때 재훈이를 도와서 영과일 회원들이 지도 어느 구역에 있더라도 성우가 피리를 불 때 ‘SAFE ZONE’에 들어갈 수 있게 하는 ‘SAFE ZONE’의 최소 개수를 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 지도의 행의 수를 나타내는 $N$ $(1 \le N \le 1,000)$ 과 지도의 열의 수를 나타내는 $M$ $(1 \le M \le 1,000)$ 이 주어진다.

두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주어진다.

지도 밖으로 나가는 방향의 입력은 주어지지 않는다.

출력

첫 번째 줄에 ‘SAFE ZONE’의 최소 개수를 출력한다.

풀이과정

1번째 시도

문제를 해결하기 위해 사용한 방식은 다음과 같다.

2차원 배열로 그래프의 정보를 입력받는다.
stack 을 이용하여 그래프를 탐색하며 내가 만든 분리 집합 자료구조인 DisjointSet 을 활용하여 ‘구역’ 들을 구분시킨다. 이 과정에서 집합의 개수를 세준다.
집합의 개수를 출력한다.

코드는 다음과 같이 작성하였다. 제출 시에는 disjoint_set.hpp 헤더 파일의 코드를 붙여넣어 제출하였으며, 코드는 내 레포지토리²에서 확인할 수 있다.

#include <bits/stdc++.h>
#include "disjoint_set.hpp"

using namespace std;

using ll = long long;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1 ,1};

int pack(int y, int x, int M);

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<vector<int>> grid(N, vector<int>(M, 0));

    for (int i=0; i<N; i++) {
        string input;
        cin >> input;

        for (int j=0; j<M; j++) {
            switch (input[j]) {
                case 'U':
                    grid[i][j] = 0;
                    break;
                case 'D':
                    grid[i][j] = 1;
                    break;
                case 'L':
                    grid[i][j] = 2;
                    break;
                case 'R':
                    grid[i][j] = 3;
                    break;
                default:
                    break;
            }
        }
    }

    vector<vector<bool>> visited(N, vector<bool>(M, false));
    vector<bool> isGroupNumber(N * M + 1, false);

    DisjointSet diset(N * M + 1, 1);
    stack<pair<pii, int>> s;
    int result = 0;

    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            s.emplace(make_pair(i, j), 0);
        }
    }

    while (!s.empty()) {
        auto curr = s.top();
        s.pop();

        auto currPos = curr.first;
        int groupNum = curr.second;

        int currY = currPos.first;
        int currX = currPos.second;

        if (!visited[currY][currX]) {
            visited[currY][currX] = true;

            int dir = grid[currY][currX];

            int nextY = currY + dy[dir];
            int nextX = currX + dx[dir];

            if (groupNum == 0) {
                result++;
                groupNum = pack(currY, currX, M);
                isGroupNumber[groupNum] = true;
            }

            int nextGroupNum = diset.find(pack(nextY, nextX, M));

            if (groupNum != nextGroupNum) {
                diset.merge(groupNum, nextGroupNum);

                if (isGroupNumber[nextGroupNum]) {
                    result--;
                }
                else {
                    s.emplace(make_pair(nextY, nextX), diset.find(groupNum));
                }
            }
        }
    }

    cout << result;

    return 0;
}

int pack(int y, int x, int M) {
    return y * M + x + 1;
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

분리 집합의 사용처가 생각보다 다양한 것 같다. 뭔가 구역를 나눈다거나 하는 문제는 어김없이 분리 집합을 사용하게 되었던 것 같고, 덕분에 사용하는게 익숙해진 것 같다.

앞으로 풀어야 할 CLASS 5 문제가 4개가 남아있는데, 연휴가 다가오는 동시에, 연속으로 군대도 다가오면서 하루에 $2$ 문제를 풀어야하나 생각중이다. 상황을 봐서 결정하도록 하겠다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/16724
2: https://github.com/ChoiCube84/baekjoon-solutions/blob/main/C%2B%2B/custom_data_structures/disjoint_set.hpp

← Previous Post Next Post →