[BOJ] 10037 : Decorating the Pastures

문제 링크

10037번: Decorating the Pastures (acmicpc.net)

10037번: Decorating the Pastures

그래프 탐색 문제.

문제 해석

농부 존은 N개의 목장을 가지고 있고, 농장은 M개의 길로 연결되어있다. 그리고 농장끼리는 최대 2개의 길로 연결될 수도 있다. 베시가 존의 생일을 축하해주기 위해 각 농장을 꾸미려고 한다. F 또는 J로 꾸밀 수 있는데, 연결되어있는 농장끼리는 서로 같은 알파벳으로 꾸밀 수 없다. 그런데 F보다 J로 꾸미는게 더 싸기 때문에 최대한 J를 많이 이용하려고 한다. 만약 조건을 지키면서 모든 농장을 꾸밀 수 없다면 -1을 출력하고, 꾸밀 수 있다면 최대 J의 개수를 출력해라.

풀이

단순한 BFS 문제 처럼 보이지만 J를 최대한 많이 이용하라는 조건이 있다. 만약 이웃 농장과 연결된 길이 하나도 없는 농장이라면 그냥 J로 꾸미면 된다. 하지만 여러 농장이 연결되어 있는 상황이라면 처음에 먼저 J로 꾸미는게 이득인지 F로 꾸미는게 이득인지 바로 판단할 수가 없다.

나는 J와 F를 숫자로 표기하기 위해서 단순히 J는 2로 F는 3으로 표기했다(이유 없음). 그래서 visited 배열을 만든 후 해당 농장의 값이 0이면 아직 꾸며지지않은 농장, 2면 J로 꾸며진 농장, 3이면 F로 꾸며진 농장으로 표기했다.

1 ~ N 까지 돌면서 해당 농장이 아직 꾸며지지 않았으면 BFS를 통해서 인접한 농장을 겹치지 않게 꾸며주었다. 처음 시작점을 J로 꾸밀지 F로 꾸밀지 모르므로 두 가지 경우 모두 해보았다. 탐색 도중에 인접한 두 칸이 똑같은 알파벳으로 꾸며지면 그때는 잘못된 경우이므로 탐색을 중단했다. 그리고 J로 시작한 경우 F로 시작한 경우 모두 유효한 경우, 즉 모든 연결된 농장이 다른 알파벳으로 꾸며진 경우 둘 중에 J를 더 많이 사용한 경우를 택했다. 반대로 두 경우 모두 유효하지 않은 경우 꾸미는 방법이 없는 경우이므로 -1을 출력한다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> Priority_queue;
const ll INF = LLONG_MAX;
const int MAX_N = 50000 + 5;
vector<int> visited(MAX_N,0);
vector<int> visited_1(MAX_N,0);
vector<int> visited_2(MAX_N,0);
vector<int> Edge[MAX_N];
int N, M;
 
int Fill_pasture(int st, int letter) {
    queue<pair<int, int>> q;
    q.push({ st,letter });
    if (letter == 2) {
        int cnt = 0;
        while (!q.empty()) {
            int now = q.front().first;
            int Letter = q.front().second;
            q.pop();
            if (visited_1[now] == Letter)
                continue;
            else if (visited[now] != 0 && visited[now] != Letter)
                return -1;
            visited_1[now] = Letter;
            if (Letter == 2)
                cnt++;
            for (int i = 0; i < Edge[now].size(); i++) {
                int next = Edge[now][i];
                int next_letter;
                if (Letter == 2)
                    next_letter = 3;
                else next_letter = 2;
                if (!visited_1[next])
                    q.push({ next,next_letter });
                else if (visited_1[next] != next_letter)
                    return -1;
            }
        }
        return cnt;
    }
    else if (letter == 3) {
        int cnt = 0;
        while (!q.empty()) {
            int now = q.front().first;
            int Letter = q.front().second;
            q.pop();
            if (visited_2[now] == Letter)
                continue;
            else if (visited[now] != 0 && visited[now] != Letter)
                return -1;
            visited_2[now] = Letter;
            if (Letter == 2)
                cnt++;
            for (int i = 0; i < Edge[now].size(); i++) {
                int next = Edge[now][i];
                int next_letter;
                if (Letter == 2)
                    next_letter = 3;
                else next_letter = 2;
                if (!visited_2[next])
                    q.push({ next,next_letter });
                else if (visited_2[next] != next_letter)
                    return -1;
            }
        }
        return cnt;
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        Edge[a].push_back(b);
        Edge[b].push_back(a);
    }
 
    for (int i = 1; i <= N; i++) {
        if (visited[i] != 0)
            continue;
        visited_1 = visited;
        visited_2 = visited;
        int cnt_1 = Fill_pasture(i, 2);
        int cnt_2 = Fill_pasture(i, 3);
        if (cnt_1 == -1 && cnt_2 == -1) {
            cout << "-1\n";
            return 0;
        }
        else if (cnt_1 >= cnt_2) {
            visited = visited_1;
        }
        else if (cnt_2 > cnt_1) {
            visited = visited_2;
        }
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        if (visited[i] == 2)
            ans++;
    }
    cout << ans << "\n";
    return 0;
}