백준 17040 The Great Revegetation (USACO February 2019 Bronze 2번)

문제 링크: https://www.acmicpc.net/problem/17040

17040번: The Great Revegetation (Bronze)

 

어떤 한 소가 좋아하는 두개의 pasture에 같은 grass를 심을수 없음.

예시에 따르면, 1번 pasture에 심을 grass의 종류는 2, 4, 5번 pasture에 심을 grass의 종류와 달라야 하고, 2번은 1, 2, 4번과 달라야 하고, 3번은 4번과 달라야 하고, 4번은 1, 2, 3번과 달라야 하고, 마지막으로 5번은 1, 2번과 달라야 함.

1 ~ n번 pasture까지 차례대로 어떤 종류의 grass를 심을건지 결정할것임.

i번째 pasture의 grass를 결정할때, grass의 종류를 1번부터 4번까지 훑으면서(smallest possible number를 출력해야 하기 때문에), 어떤 grass를 심을수 있는지 결정하면 됨.

#include <bits/stdc++.h>
using namespace std;
 
int n, m, ans[101];
vector<int> v[101];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
 
    for(int i = 1; i <= n; i++) {
        for(int g = 1; g <= 4; g++) {
            bool flag = 1;
            for(int j = 0; j < v[i].size(); j++)
                if(ans[v[i][j]] == g) flag = 0;
            if(flag) {
                ans[i] = g;
                break;
            }
        }
    }
 
    for(int i = 1; i <= n; i++)
        cout << ans[i];
    cout << '\n';
    return 0;
}