[BOJ] 16724: 피리 부는 사나이 (C/C++)

문제 16724번: 피리 부는 사나이

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

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

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

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

입력

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

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

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

출력

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

문제분석

문제 요구사항

• SAFE ZONE의 최소 갯수를 구하여 함 -> 같은 SAFE ZONE을 공유하는 좌표들을 한개의 Set으로 분류가능
• 지도의 좌표를 Node, 지도의 방향을 Edge로 보면 Directed Graph로 해석가능.

지도를 일종의 Graph로 해석하고 같은 SAFE ZONE을 공유하는 좌표들을 Set으로 본다면 Disjoint Set를 이용하여 풀이 할 수 있다.

구현

각각의 좌표를 1개의 단일 Set으로 해석 한 후, MergeSet이 일어날 때 마다, Set의 갯수를 1씩 줄인다.
Merge Set의 경우 현재 좌표의 Set이 이동하는 좌표의 Set으로 Merge된다고 구현한다.

증명

모든 Sets을 merge 한 후, 최종적으로 남는 set의 형태는 크게 2개로 정의 할 수 있다.

1. 1개 이상의 시작점을 가지며, Terminal을 가지는 Graph의 형태.
2. 1개 이상의 시작점을 가지며, Graph안에 Cycle을 가지는 형태.

최종적으로 이 2가지 형태로 정의 할 수 있다.
1번의 경우 Terminal에 SAFE ZONE을 설치 하면 되고, 2번의 경우 Cycle 내부의 한 Node에 SAFE ZONE을 설치하게 되면, graph 내부의 모든 Node들에서 SAFE ZONE에 접근 가능하다.
따라서 총 Disjoint Set의 갯수는 SAFE ZONE의 갯수와 동일하다.

코드

#include <iostream>
#include <string>
#include <utility>
#include <vector>

int N, M;

int cnt_sets;
std::vector<int> sets;

const int ConvertToSet(const std::pair<int, int>& p) {
  return p.first * M + p.second;
}

const int GetSet(const int set_index) {
  if (sets[set_index] == set_index) {
    return set_index;
  }

  return sets[set_index] = GetSet(sets[set_index]);
}

void MergeSet(int lset, int rset) {
  lset = GetSet(lset);
  rset = GetSet(rset);

  if (lset != rset) {
    sets[lset] = rset;
    cnt_sets--;
  }

  return;
}

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

  std::cin >> N >> M;

  cnt_sets = N * M;
  sets.assign(N * M, 0);
  for (int i = 0; i < sets.size(); ++i) {
    sets[i] = i;
  }

  std::string input;
  for (int i = 0; i < N; ++i) {
    std::cin >> input;
    for (int j = 0; j < M; ++j) {
      const std::pair<int, int> now_pos(i, j);
      std::pair<int, int> next_pos(now_pos);
      if (input[j] == 'U') {
        next_pos.first--;
      } else if (input[j] == 'D') {
        next_pos.first++;
      } else if (input[j] == 'L') {
        next_pos.second--;
      } else {
        next_pos.second++;
      }

      MergeSet(ConvertToSet(now_pos), ConvertToSet(next_pos));
    }
  }

  std::cout << cnt_sets;

  return 0;
}