[프로그래머스] 양과 늑대 (C++)

공부 스파이럴·2023년 11월 17일

프로그래머스

목록 보기

6/18

문제

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

※ 주의

더 좋은 코드가 있어서 개선점 위주로 작성

아이디어 1

트리를 만들자

(※ 사실 안 만들어도 됨)

root 노드와 단방향 그래프가 주어져 있기 때문에 인접 행렬을 만들어서 트리를 만들기 쉬움

개선점 : 오히려 root 노드와 단방향 그래프가 주어져 있기 때문에 굳이 트리를 만들지 않고 인접행렬 자체를 이용해도 됨

양방향 그래프가 주어져 있고 balanced tree를 직접 만들 필요가 있을 때 트리를 구현해야할 듯

인접행렬

vector<vector<int>> adj((int)info.size(), vector<int>((int)info.size(), 0)); // Adjacency Matrix
    for (int i = 0; i < edges.size(); ++i)
        adj[edges[i][0]][edges[i][1]] = 1;

개선점 : 굳이 n x n 행렬을 만들 필요 없이 있는 간선 정보만 push_back으로 넣어도 됐음
2차원 array가 아닌데 벡터에 대한 활용이 부족했던 듯

트리

template<class T>
void safe_delete(T*& ptr)
{
    if (ptr != nullptr)
    {
        delete ptr;
        ptr = nullptr;
    }
}

class node {
public:
    explicit node(int info, int num)
        : m_info(info),
        m_num(num)
    {
    }
    ~node()
    {
        for (auto& c : m_vChild)
            safe_delete(c);
        m_vChild.clear();
    }
    
public:
    void insert_node(vector<vector<int>>& adj, const vector<int>& info)
    {
        for (int i = 0; i < adj.size(); ++i)
        {
            if (adj[m_num][i] == 1)
            {
                adj[m_num][i] = 0;
                node* child = new node(info[i], i);
                m_vChild.push_back(child);
                child->insert_node(adj, info);
            }
        }
    }
    
private:
    int m_info;
    int m_num;
    
    vector<node*> m_vChild;
};

아이디어 2

모든 순회를 해보자
서브 트리를 왔다 갔다 해야 하기 때문에 BFS나 DFS로는 모든 순회를 표현할 수 없음

n!의 순회를 모두 검사하는 것은 존재하지 않는 순회도 있기 때문에 비효율적
순열 느낌으로 모든 경우를 확인
> 현재 queue : 1
삽입할 노드 : 2 3
#
- 2 1
  - 3 2 1
  - 2 3 1
  - 2 1 3
- 1 2
  - 3 1 2
  - 1 3 2
  - 1 2 3
개선점 : set을 이용하면 복잡하게 구현할 필요없이 다 집어넣고 하나씩 전부 빼가면서 사용하면 됨
list 사용에 너무 사로잡혀서 코드도 더럽고 개선도 일반화도 안됨
> set을 이용 시
1 2 3
erase(1)

erase(2)

erase(3)

erase(3)

erase(2)

erase(2)

erase(1)

erase(3)

erase(3)

erase(1)
erase(3)

erase(2)

erase(1)

erase(1)

erase(2)

순회

    void permutation_search(list<node*> queue, int num_sheep, int num_wolf, int& num_max)
    {
        if (queue.size() == 0)
            return;
        
        node* cur_node = queue.front();
        queue.pop_front();
        
        if (cur_node->m_info == 0)
        {
            num_sheep++;
            num_max = max(num_max, num_sheep);
        }
        else
        {
            num_wolf++;
            if (num_wolf >= num_sheep)
                return;
        }
        
        switch (cur_node->m_vChild.size())
        {
            case 1:
                for (auto iter = queue.begin(); iter != queue.end(); iter++)
                {
                    queue.insert(iter, cur_node->m_vChild[0]);
                    permutation_search(queue, num_sheep, num_wolf, num_max);
                    iter--;
                    iter = queue.erase(iter);
                }
                
                queue.push_back(cur_node->m_vChild[0]);
                permutation_search(queue, num_sheep, num_wolf, num_max);
                queue.pop_back();
                break;
                
            case 2:
                for (auto iter = queue.begin(); iter != queue.end(); iter++)
                {
                    queue.insert(iter, cur_node->m_vChild[0]);
                    for (auto iter2 = queue.begin(); iter2 != queue.end(); iter2++)
                    {
                        queue.insert(iter2, cur_node->m_vChild[1]);
                        permutation_search(queue, num_sheep, num_wolf, num_max);
                        iter2--;
                        iter2 = queue.erase(iter2);
                    }
                    
                    queue.push_back(cur_node->m_vChild[1]);
                    permutation_search(queue, num_sheep, num_wolf, num_max);
                    queue.pop_back();
                    
                    iter--;
                    iter = queue.erase(iter);
                }
                
                queue.push_back(cur_node->m_vChild[0]);
                for (auto iter2 = queue.begin(); iter2 != queue.end(); iter2++)
                {
                    queue.insert(iter2, cur_node->m_vChild[1]);
                    permutation_search(queue, num_sheep, num_wolf, num_max);
                    iter2--;
                    iter2 = queue.erase(iter2);
                }
                    
                queue.push_back(cur_node->m_vChild[1]);
                permutation_search(queue, num_sheep, num_wolf, num_max);
                queue.pop_back();
                queue.pop_back();
                break;
                
            default:
                permutation_search(queue, num_sheep, num_wolf, num_max);
                break;
        }
    }

실행 코드

    node* root = new node(info[0], 0);
    root->insert_node(adj, info);
    
    list<node*> queue;
    queue.push_back(root);
    
    root->permutation_search(queue, 0, 0, answer);
    
    safe_delete(root);