[백준/C++] 우수 마을 (No. 1949)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

 

이 문제는 사실 잘 보면 트리의 독립집합 문제와 크게 다를게 없는 문제다.

 

문제의 조건을 정리하면

 

우수 마을이 아닌 마을은 주변에 적어도 하나의 우수마을이 있어야 하며, 우수 마을인 마을은 인접한 마을에 우수 마을이 있으면 안된다.

 

그림을 보며 조건에 대해 생각해보자

 

위 그림과 같은 트리가 있을 경우 A마을이 우수 마을이면 B,C,D 마을은 우수 마을이 되면 안된다.

그러므로 A마을이 우수 마을인 경우에는 B, C, D 마을이 우수마을이 아닌 경우의 최대값을 더하면 된다.

 

반대로 A 마을이 우수마을이 아닌 경우에는 B, C, D 마을은 우수마을이어도 되고, 우수마을이 아니어도 된다.

그러므로 A 마을이 우수마을이 아닌 경우에는 B, C, D 마을이 우수 마을인 경우와 아닌 경우를 비교해 더 큰 값을 더하면 된다.

 

이렇게 단순히 최대값을 더할 수 있는 이유는 모든 최대값의 경우가 위 두 경우에 해당하기 때문이다.

 

만약 B, C, D마을도 우수마을이 아니며, A마을도 우수마을이 아닌 경우가 최대값을 만드는 경우를 생각해보자.

 

이 경우는 A마을이 우수마을이 아닌 경우에 포함된다.

왜냐하면 A마을이 우수마을이 아닐 때 B, C, D 마을이 우수 마을이거나 우수 마을이 아닌 경우를 비교해 더하기 때문이다.

 

그러므로 (B 마을이 우수마을인 경우) < (B 마을이 우수마을이 아닌경우) 가 성립하므로 자동적으로 경우에 포함된다.

 

다른 경우도 생각해보면 마찬가지로 A마을이 우수 마을이거나 아닌 경우에 포함됨을 알 수 있다.

 

+ 여기서 조건에 만족하지 않는 경우가 생길 수 있지 않을까? 의문이 들 수 있다.

그러면 A, B, C, D 마을이 우수마을이 아니며, S마을도 우수마을이 아닌 경우가 최대값이라고 가정해 보자.

그렇다면 이 경우에 A마을을 우수마을로 선정해도 조건에 위배되지 않는 다는 사실을 알 수 있다.

그러므로 최대값+A마을의 인원이 조건을 만족하는 최대값이 되므로 "A, B, C, D 마을이 우수마을이 아니며, S마을도 우수마을이 아닌 경우가 최대값"이라는 가정은 위배된다.

 

 

 

​

[아이디어 정리]

1. 특정 노드를 기준으로 트리를 그린다.
2. 트리를 그린 후 반환 값은 현재 마을이 우수마을인 경우, 우수마을이 아닌 경우의 최대값을 return 한다.
3. return 받을 값을 바탕으로 현재 마을이 우수 마을인 경우에는 자식 마을이 전부 우수마을이 아닌 경우를 더하고, 현재 마을이 우수마을이 아닌 경우에는 자식 마을이 우수마을이거나, 우수마을이 아닌 경우를 비교해 더 큰 값을 더한다.
4. 최종적으로 루트노드가 우수마을인 경우와 우수마을이 아닌 경우를 비교해 더 큰 값을 출력한다.

 

 

 

Code

 

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

bool canGo(vector<int>& map, vector<int>limitD, vector<int>dx, int nD, int limitIdx, int seat)
{
    int nS = seat + dx[limitIdx];
    if (limitIdx % 2 == 0)
    { // 위로 +
        if (seat % limitD[nD] + dx[limitIdx] < limitD[nD] && map[nS] == 0) {
            map[nS] = 1;
            return true;
        }
    }
    else { //아래로
        if (seat % limitD[nD] >= dx[nD * 2] && map[nS] == 0) {
            map[nS] = 1;
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    vector<int> nDemension;
    int d;
    for (int i = 0; i < 11; i++) {
        cin >> d;
        if (d > 1) {
            nDemension.push_back(d);
        }
    }

    int moveF = 1;
    vector<int> dx;
    vector<int> limitD(nDemension.size());
    for (int i = 0; i < nDemension.size(); i++) {
        dx.push_back(moveF);
        dx.push_back(-moveF);
        moveF *= nDemension[i];
        limitD[i] = moveF;
    }
    vector<int>map(moveF);
    queue<pair<int, int>> q;
    int toma = 0;
    for (int i = 0; i < moveF; i++) {
        cin >> map[i];
        if (map[i] == 1) {
            q.push({ i, 0 });
        }
        else if (map[i] == 0) {
            toma += 1;
        }
    }

    pair<int, int> np;
    int lstD = 0;
    while (!q.empty()) {
        np = q.front();
        lstD = np.second;
        q.pop();
        for (int i = 0; i < nDemension.size(); i++) {
            for (int j = 0; j < 2; j++) {
                if (canGo(map, limitD, dx, i, i * 2 + j, np.first))
                {
                    q.push({ np.first + dx[i * 2 + j] , np.second + 1 });
                    toma -= 1;
                }
            }
        }
    }
    if (toma == 0) {
        cout << lstD;
        return 0;
    }
    cout << -1;
    return 0;
}

 

---

처음에 문제를 보고 현재 마을이 우수마을이 아닐 경우 자식 마을중에 우수 마을이 있는 경우와 자식마을 중에 우수마을이 없는 경우를 나누어서 생각해야되나 고민 했다. 

근데 경우의 수를 잘 생각해보니 최대값을 비교하면 두 경우를 나눌 필요가 없다는 사실을 깨닫고 바로 해결했다...

문제의 조건을 보고 생각을 깊게 할 필요가 있는 좋은 문제였다.

 

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