취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 21236번 문제인 Comfortable Cows이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/21236

소가 총 10만마리이므로, 자료가 포함되어있는지 확인하거나, 몇 개가 들어있는지 세는 쿼리를 O(lgN)에 처리할 수 있는 set과 multiset 자료구조를 이용하여 O(NlgN)의 시간복잡도로 문제를 해결할 수 있다.

이 문제는 더 나은 복잡도로도 해결할 수 있으나, 이 문제는 USACO 브론즈 문제이므로 최대한 단순하게 구현하고자 하였다.

set과 multiset을 이용하면, 다음을 반복하여 문제를 해결할 수 있다.

1) 점을 입력받는다.

2) set에 점을 추가한다.

3) multiset에 이 점이 3개가 있다면 출력하는 답이 1 증가한다. (이 소는 Comfortable하기 때문이다.)

4) multiset에 (위/아래/왼쪽/오른쪽) 점을 각각 추가한다.

5) (위/아래/왼쪽/오른쪽) 점이 set에 존재할 때:

5-1) multiset에 그 점이 3개가 있다면 출력하는 답이 1 증가한다. (그 순간 그 점에 있는 소가 Comfortable해진다.)

5-2) multiset에 그 점이 4개가 있다면 출력하는 답이 1 감소한다. (그 순간 그 점에 있는 소가 not Comfortable해진다.)

위의 문제풀이 방식이 타당한 이유는 천천히 생각하면 간단히 알 수 있을 것이다.

set과 multiset에 점을 저장하기 위하여 pair를 이용하였다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <set>
#include <vector>
using namespace std;

multiset<pair<int, int>> mset;
set<pair<int, int>> SET;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    int cnt = 0;
    for (int i = 0;i < N;i++) {
        int x, y; cin >> x >> y;
        SET.insert({ x,y });
        if (mset.count({ x,y }) == 3) cnt++;
        mset.insert({ x - 1,y });
        if (SET.find({ x - 1,y }) != SET.end()) {
            int msetcount = mset.count({ x - 1,y });
            if (msetcount == 3) cnt++;
            else if (msetcount == 4) cnt--;
        }
        mset.insert({ x + 1,y });
        if (SET.find({ x + 1,y }) != SET.end()) {
            int msetcount = mset.count({ x + 1,y });
            if (msetcount == 3) cnt++;
            else if (msetcount == 4) cnt--;
        }
        mset.insert({ x,y - 1 });
        if (SET.find({ x,y - 1 }) != SET.end()) {
            int msetcount = mset.count({ x,y - 1 });
            if (msetcount == 3) cnt++;
            else if (msetcount == 4) cnt--;
        }
        mset.insert({ x,y + 1 });
        if (SET.find({ x,y + 1 }) != SET.end()) {
            int msetcount = mset.count({ x,y + 1 });
            if (msetcount == 3) cnt++;
            else if (msetcount == 4) cnt--;
        }
        cout << cnt << '\n';
    }
}