[C++] [2025 프로그래머스 코드챌린지 1차 예선] 4번 / 홀짝트리

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/388354

프로그래머스

 

 

문제 3줄 요약

1. 루트 노드에 따라 홀수 / 짝수 / 역홀수 / 역짝수 노드가 정의된다.

2. 트리는 어떤 노드를 루트로 설정하느냐에 따라 홀짝 / 역홀짝 트리가 모두가 될 수 있거나 모두가 될 수 없을 수 있다.

3. 각 트리에 대해 루트 노드를 설정했을 때, 홀짝 트리와 역홀짝 트리의 개수를 구하려 한다.

 

---

 

 

도대체 이게 무슨 소리일까..

 

문제 자체가 참 읽으면서도 이해가 힘들어

몇 번이고 되읽었다.

 

예시를 참고하니 이해에 조금이나마 도움이 됐다.

 

같이 살펴보자!

 

 

위의 트리는

루트 노드를 3으로 설정한다면, 좌측 하단의 이미지 처럼

루트 노트를 6으로 설정한다면, 우측 하단의 이미지 처럼 그려질 것이다.

 

 

여기서 노란색 노드들은

홀수 또는 짝수 노드들을 나타내고 있다.

 

 

홀수 / 짝수 노드는

노드의 번호와 자식의 노드 개수가 같은 홀수 / 짝수인 경우이다.

 

 

빨간색 노드들은

역홀수 또는 역짝수 노드들을 나타낸다.

 

 

노드의 번호와 자식의 노드 개수의 홀수 / 짝수가 다른 경우는

역홀수 / 역짝수 노드가 된다.

 

 

 

여기서 좌측 이미지와 같이

모든 노드가 홀수 또는 짝수 노드인 경우를

홀짝 트리로 정의

 

모든 노드가 역홀수 또는 역짝수 노드인 경우는

역홀짝 트리라고 정의한다.

 

우측 이미지는

홀짝 트리와 역홀짝 트리 두 가지 모두가 될 수 없다.

 

---

 

 

그럼 우리는 어떤 코드를 작성해야 할까?

 

우리에게 필요한 것은

1. 트리 탐색

2.홀짝 or 역홀짝 노드 체크

3. 홀짝 및 역홀짝 트리 카운트

정도로 나눠서 생각해볼 수 있겠다.

 

 

그럼

트리 탐색부터 구현해보자!

 

int bfs(int r){
    queue<int> q;
    q.push(r);
    visited[r]=true;
    int checkNode = 0;
    checkNode = check(r, m[r].size(), checkNode);
    
    while(!q.empty())
    {
        int nxt = q.front();
        q.pop();
        
        for(int mm : m[nxt])
        {
            if(!visited[mm])
            {
                q.push(mm);
                visited[mm]=true;
                checkNode = check(mm, m[mm].size()-1, checkNode);
                if(checkNode==-1) return -1;
            }
        }
    }
    
    return checkNode;
}

 

 

트리 탐색은 BFS를 통해 진행하였다.

루트 노드로 설정할 번호를 인자로 받아주어 초기값으로 설정한다.

 

 

check 함수는 홀짝 및 역홀짝 노드 중 어떤 것인지 판별한다.

이후 큐에 통해 자식 노드들을 탐색하며

자식 노드들의 홀짝 및 역홀짝 노드를 체크한다.

 

 

이때 크기를 -1을 하고 check 함수에 넘겨주는데,

이는 부모 노드의 개수는 제외하고 본인이 갖고 있는 자식 노드 개수만 고려하기 위해서 이다.

(간선을 연결하는 코드에서 서로에게 간선이 있다고 설정했기 때문에)

 

 

여기서 checkNode가 -1 이면, 탐색을 종료하고 -1을 반환하는데

-1은 무엇을 의미하는지 check 함수를 살펴보자.

 

int check(int num, int size, int cur){
    if(num%2 == size%2) {
        if(cur==2)
        {
            return -1;
        }
        return 1;
    }
    else if(num%2 != size%2) {
        if(cur==1)
        {
            return -1;
        }
        return 2;
    }
}

 

판별할 때 필요한

노드의 번호, 자식 노드의 개수, 현재 노드의 상태를

인자로 받아온다.

 

문제에서 노드의 정의는

홀수 노드 / 짝수 노드 / 역홀수 노드 / 역짝수 노드

4가지 이지만,

코드에서는 홀짝 노드와 역홀짝 노드로 묶어서 처리할 것이다.

 

노드의 번호와 자식 노드 개수의 홀수/짝수가 같다면,

홀짝 노드이고 1을 반환한다.

 

노드의 번호와 자식 노드 개수의 홀수/짝수가 다르다면,

역홀짝 노드이고 2를 반환한다.

 

 

 

현재의 노드 상태는 왜 필요할까?

이전에 판별했던 노드의 상태와 현재 노드의 상태가 다르다면

그 트리는 홀짝 트리와 역홀짝 트리 모두가 될 수 없다.

 

따라서 그 경우에는

-1을 반환하고 BFS에서도 -1을 반환하며 탐색을 바로 종료한다.

 

만일 모든 탐색을 종료하고

1을 반환했다면, 홀짝 트리

2를 반환했다면, 역홀짝 트리가 되겠다.

 

---

 

코드를 종합해보면 아래와 같이 작성할 수 있겠다.

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> m[1000001];
bool visited[1000001];

int check(int num, int size, int cur){
    if(num%2 == size%2) {
        if(cur==2)
        {
            return -1;
        }
        return 1;
    }
    else if(num%2 != size%2) {
        if(cur==1)
        {
            return -1;
        }
        return 2;
    }
}

int bfs(int r){
    queue<int> q;
    q.push(r);
    visited[r]=true;
    int checkNode = 0;
    checkNode = check(r, m[r].size(), checkNode);
    
    while(!q.empty())
    {
        int nxt = q.front();
        q.pop();
        
        for(int mm : m[nxt])
        {
            if(!visited[mm])
            {
                q.push(mm);
                visited[mm]=true;
                checkNode = check(mm, m[mm].size()-1, checkNode);
                if(checkNode==-1) return -1;
            }
        }
    }
    
    return checkNode;
}

vector<int> solution(vector<int> nodes, vector<vector<int>> edges) {
    vector<int> answer = {0,0};
    
    for(auto edge : edges)
    {
        m[edge[0]].push_back(edge[1]);
        m[edge[1]].push_back(edge[0]);
    }
    
    for(int root : nodes)
    {
        int idx = bfs(root);
        if(idx != -1) answer[idx-1]++;
        fill(visited, visited+1000001, false);
    }
    
    return answer;
}

 

처음에는 노드의 종류 4가지를 모두 고려하다보니

코드가 길어지기도 하고 복잡했으나

간소화하여 접근하니 보다 쉽게 해결할 수 있었다.

 

특히

check하는 부분에서 자식의 노드인 경우에는 부모의 노드 개수는 제외하고 체크하는게

중요한 포인트라고 생각되는 문제였다.

 

끝!