[백준 / BOJ] C++ 16567 바이너리 왕국

16567번: 바이너리 왕국

 

문제

https://www.acmicpc.net/problem/16567

16567번: 바이너리 왕국

 

 

풀이

이어져 있는 더러운 칸을 하나의 집합이라 했을 때 몇 개의 집합이 있는지 카운트 수를 유지해 주면 된다. 현재 상태를 입력받을 때 N+2 크기의 배열을 만들어 0번 index와 N+1번 인덱스는 0으로 두고 1~N번 인덱스에 수를 입력받는다. 왼쪽부터 차례로 입력을 받으므로 입력이 더러운 칸일 때, 왼쪽 칸이 깨끗한 칸인 경우 카운트를 1 증가시킨다.

 

이후 M번의 쿼리에서 0이 입력된 경우 카운트 수를 출력하면 되고 1이 입력된 경우 더럽힐 칸의 번호를 입력받는다. 더럽힐 칸이 이미 더럽혀져 있다면 다음 쿼리로 넘어가고, 깨끗한 칸이라면 더럽히고 다음 작업을 수행한다.

1. 새로 더럽혀진 칸의 왼쪽과 오른쪽이 모두 더러운 칸이면 두 집합이 이어진다.
2. 새로 더럽혀진 칸의 왼쪽과 오른쪽이 모두 깨끗한 칸이면 새로운 집합이 생긴다.
3. 위 두 조건을 모두 만족하지 않는 경우(새로 더럽혀진 칸의 왼쪽과 오른쪽 중 한 쪽만 더러운 칸인 경우) 집합의 수는 유지된다.

따라서 이전 칸, 다음 칸이 더러운 칸인지 확인하고 1인 경우 카운트 수를 1 감소, 2인 경우 카운트 수를 1 증가시킨다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, M, cnt = 0;
  cin >> N >> M;
  vector<int> v(N + 2, 0);
  for (int i = 1; i <= N; i++) {
    cin >> v[i];
    if (v[i] && !v[i - 1])
      cnt++;
  }
  while (M--) {
    int a, b;
    cin >> a;
    if (!a) {
      cout << cnt << '\n';
    } else {
      cin >> b;
      if (v[b])
        continue;
      v[b] = 1;
      if (v[b - 1] && v[b + 1])
        cnt--;
      else if (!v[b - 1] && !v[b + 1])
        cnt++;
    }
  }
  return 0;
}