[c++] 백준 1693 - 트리 색칠하기

0. [c++] 백준

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

1. 풀이

처음 풀이는 매우 간단하게 시작했었다. 사실 노드를 칠하는데 2가지 색상이면 충분하기에 2가지 색상을 반복해서 칠하는 방법을 고안했었는데, 예제부터 틀리기에 아닌 것을 깨닫고...

하지만, 이를 칠하는 것에 색이 한정적으로 쓰일 것 같아 조금 찾아보았는데,  http://codersbrunch.blogspot.com/2017/07/1693.html를 보니 n개의 노드를 칠하는데 대략 종류의 색밖에 필요 없다는 것을 알 수 있었다.

이를 활용해서 코드를 짜보았다.

우선 동적계획법을 활용하여 코드를 완성하였고, adj[i]는 i와 연결된 노드를 담는 노드인데, 양방향을 전부 담았다.

이렇게 구현한 이유는 처음 입력으로는 root에서 뻗어나가는 방향을 확정시킬 수 없기 때문에 이와같이 만들었다.

원래 이와같이 만들면서 bool visited[]라는 방문을 확인하는 방법을 대게 활용했었는데, 이 대신에 자신이 이전에 어디서 왔는지에 대한 출처를 함수에 추가해주었다.

이를 활용하여 자신이 다시 뒤로 빠져나가는 대참사가 발생하지 않도록 만들어주었다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

#include<iostream> #include<vector>   using namespace std;   //adj[i]는 i와 연결된 노드를 담는다. vector<int> adj[100001]; int cache[100001][19]; const int INF = 100000007;   int Min(int a, int b) {     return a < b ? a : b; }   int dp(int here, int beforeNode,int color) {     //메모이제이션을 활용하자.     int& ret = cache[here][color];     //기저 사례 : 이미 색칠이 된 경우 바로 리턴     if (ret != 0)          return ret;     int colorSum = 0;     for (int i = 0; i < adj[here].size(); i++) {         int there = adj[here][i];         int min = INF;         //이전 노드를 방문하지 않도록 한다.         if (there != beforeNode) {             for (int nextColor = 1; nextColor <= 18; nextColor++)                 //다음 노드의 색은 이번 노드의 색과 겹치지 않게 한다.                 if (color != nextColor)                     min = Min(min, dp(there, here, nextColor));             colorSum += min;         }              }     return ret = colorSum + color; }   int main() {     int N,a,b;     cin >> N;     for (int i = 1; i < N; i++) {         cin >> a >> b;         //인접 노드를 양쪽 모두에 담는다.(방향을 확정시킬 수 없기 때문이다.)         //만일 위에서 부터 쫘쫘작 주어진다면, 사실 한쪽만 담아도 상관 없다.         adj[a].push_back(b);         adj[b].push_back(a);     }     int min = INF;     for (int i = 1; i <= 18; i++) {         min = Min(min, dp(1,0,i));     }       cout << min;       return 0; } Colored by Color Scripter

cs

3. 참고

http://codersbrunch.blogspot.com/2017/07/1693.html

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!