프로그래머스 Level 3 홀짝트리

홀짝트리 (프로그래머스 Level 3)

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

level 3 문제를 다소 오랜만에 푼것인지는 몰라도 구현에 다소 시간이 걸렸던 것 같다

홀수,짝수, 역홀수,역짝수 노드 와 홀짝 트리, 역홀짝 트리 라는
다소 복잡해 보일수 있는 정의를 몇가지 해두고
그것에 맞게 그래프를 탐색하는 문제이다

문제가 다소 복잡해 보이는데
주요한 요점을 정리하자면,

1. ‘트리’가 주어지기에 해당 그래프 내에 ‘사이클’이 존재하지 않음을 단언할 수 있음
   
2. 노드의 ‘번호’는 바뀌지 않는다.
   
3. 트리의 ‘root’ 노드가 되는 경우는 자신의 ‘노드 상태’가 바뀌지 않지만,
   그 외에는 정 과 역이 스위칭 된다
   (홀 <-> 역홀 , 짝 <-> 역짝)
   
   • 조금 깊이 생각해본다면 파악할 수 있는 부분으로
     tree의 root 노드만이 child 들을 오롯이 가지고,
     나머지들은 ‘부모’로 선정된 것을 자신의 child 에서 제외해야 하기에
     child의 길이가 -1 되어, 자신의 반대 상태가 된다
     

그렇기에 아래와 같은 순서로 풀었다

1. node 들에게 자신의 상태를 미리 저장시켜 놓는다
   
2. 번갈아가면서 node를 root 로 만들며 bfs 탐색
   
3. 해당 tree를 탐색할때, root 노드가 아니면 switch 해서 탐색한다
   (이 때, 시간 절약을 위해, root의 상태를 보고 홀짝 트리인지 역홀짝 트리인지 판별하고
   자식이 이와 다른 상태라면 바로 return 시킨다)
   

실제 코드 구현은 조금 복잡하다
뭔가 enum과 struct 등을 사용하고자 하는 면이 있어서
코드가 길어지는 듯하다. (그렇다고 가독성이 나아지냐 한다면 그것도 잘 모르겠다)
(상당히 아슬아슬하게 통과하였기에 더 최적화할 부분이 남았거나, 다른 방식으로 풀수도 있을듯 하다)

Code

#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

enum nodeStates
{
    odd,
    even,
    rOdd,
    rEven,
};

struct nodeInfo
{
    int nodeNum;
    vector<int> childs;
    nodeStates state;

    nodeStates getState(bool isRoot = false)
    {
        if (isRoot)
            return state;

        switch (state)
        {
        case odd:
            return nodeStates::rOdd;
        case even:
            return nodeStates::rEven;
        case rOdd:
            return nodeStates::odd;
        case rEven:
            return nodeStates::even;
        }

        return state;
    }
};

// 0 : 홀짝 트리, 1 : 역홀짝 트리, -1 : 아무것도 아님
int findTrees(unordered_map<int, nodeInfo>& graphs,int rootNum)
{
    unordered_set<int> visited;
    bool bIsOddTree = false; 

    switch (graphs[rootNum].getState(true))
    {
    case odd:
    case even:
        bIsOddTree = true;
        break;
    default:
        break;
    }

    queue<int> q;
    for (int n : graphs[rootNum].childs)
    {
        q.push(n);
    }

    visited.insert(rootNum);

    while (q.empty() == false)
    {
        nodeInfo& n = graphs[q.front()];
        q.pop();

        if (visited.find(n.nodeNum) != visited.end())
            continue;

        visited.insert(n.nodeNum);

        nodeStates ns = n.getState();
        if ((bIsOddTree && (ns == rOdd || ns == rEven)) ||
            (bIsOddTree == false && (ns == odd || ns == even)))
                return -1;

        for (int nextN : n.childs)
        {
            q.push(nextN);
        }
    }

    if (bIsOddTree)
        return 0;

    return 1;
}

vector<int> solution(vector<int> nodes, vector<vector<int>> edges) {
    vector<int> answer(2,0);
    unordered_map<int, nodeInfo> graphs;

    for (int node : nodes)
    {
        graphs[node].nodeNum = node;
    }

    for (vector<int>& edge : edges)
    {
        int v1 = edge[0];
        int v2 = edge[1];

        graphs[v1].nodeNum = v1;
        graphs[v1].childs.push_back(v2);
        graphs[v2].nodeNum = v2;
        graphs[v2].childs.push_back(v1);
    }

    for (auto& g : graphs)
    {
        nodeInfo& n = g.second;

        if (n.nodeNum % 2 == 1)
        {
            if (n.childs.size() % 2 == 1)
            {
                n.state = nodeStates::odd;
            }
            else
            {
                n.state = nodeStates::rOdd;
            }
        }
        else
        {
            if (n.childs.size() % 2 == 0)
            {
                n.state = nodeStates::even;
            }
            else
            {
                n.state = nodeStates::rEven;
            }
        }
    }

    for (int node : nodes)
    {
        int v = findTrees(graphs, node);
        if (v == 0)
            answer[0]++;
        if (v == 1)
            answer[1]++;

    }

    return answer;
}