[programmers] Lv.4 동굴 탐험(c++)

4단계는 어려운거같다...

코드를 봐도 cycle을 의미한다하여 응? 왜 그게 cycle을 의미하는건데? 근본적인 질문이 떠오르고

내 방식대로 하려하면 왠지 너무 복잡해진다. 근데 대부분의 답은 내 방식대로 한게 맞는거같다..

검색하다가 위상정렬(topology sort)라는 것을 알게됐다.

(이 해설에 들어갔다가 알게됨 : https://2jinishappy.tistory.com/200, 풀이는 참고하지 않았고, 검색해서 찾아낸 위상 정렬을 설명해주고있는 아래 참고 링크에서 sort 원리만 참고했다.)

다른 방법들도 있는것 같았지만, 이게 제일 명확했다.

 

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

using namespace std;

bool topology_sort(vector<vector<int>>& di, vector<int>& indegree){
    queue<int> que;
    que.push(0);
    
    for(int i=0; i<di.size(); i++){
        if(que.empty()) return false; // cycle 발생
        
        int room = que.front(); que.pop();
        for(auto to : di[room]){
            if(--indegree[to] == 0) que.push(to);
        }
    }
    return true;
}

bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    vector<vector<int>> undirected(n);
    for(auto p: path){
        undirected[p[0]].push_back(p[1]);
        undirected[p[1]].push_back(p[0]);
    }
    
    vector<vector<int>> directed(n);
    vector<int> indegree(n, 0); indegree[0] = 0;
    queue<int> que; que.push(0);
    vector<bool> visit(n, false); visit[0] = true;
    while(!que.empty()){
        int room = que.front(); que.pop();
        for(auto to : undirected[room]){
            if(visit[to]) continue;
            que.push(to);
            directed[room].push_back(to);
            visit[to] = true;
            indegree[to]++;
        }
    }
    
    for(auto o: order){
        if(o[1] == 0) return false;
        directed[o[0]].push_back(o[1]); // o[0]을 방문한 뒤 o[1]을 감
        indegree[o[1]]++;
    }
    
    return topology_sort(directed, indegree); // learned
}

---

문제

https://programmers.co.kr/learn/courses/30/lessons/67260

코딩테스트 연습 - 동굴 탐험

728x90

---

[접근]

topology sort(링크 추가 예정)

참고: https://m.blog.naver.com/ndb796/221236874984

BFS

https://jolly-note.tistory.com/63

BFS (Breadth First Search, 너비 우선 탐색)

---

[접근1]

우선 서로 가리키는 graph를 만들고,

그것을 바탕으로 한쪽 방향으로 graph를 만든다.

거기에 order를 추가하여 cycle의 여부를 판단할 수 있게 한다.

vector<vector<int>> undirected(n);
for(auto p: path){
    undirected[p[0]].push_back(p[1]);
    undirected[p[1]].push_back(p[0]);
}

vector<vector<int>> directed(n);
vector<int> indegree(n, 0); indegree[0] = 0;
queue<int> que; que.push(0);
vector<bool> visit(n, false); visit[0] = true;
while(!que.empty()){
    int room = que.front(); que.pop();
    for(auto to : undirected[room]){
        if(visit[to]) continue;
        que.push(to);
        directed[room].push_back(to);
        visit[to] = true;
        indegree[to]++;
    }
}
    
for(auto o: order){
    if(o[1] == 0) return false;
    directed[o[0]].push_back(o[1]); // o[0]을 방문한 뒤 o[1]을 감
    indegree[o[1]]++;
}

indegree란, 앞의 참고 링크에서 볼 수 있듯, 해당 노드를 가리키는 노드의 수라고 할 수 있다.

---

[접근2]

topology sort를 해준다.

만약 n번을 다 돌기 전에 queue가 비었다면, 모든 노드를 돌지 않았다는것이므로 false를 리턴해준다.

node를 하나씩 빼면서 이어진 선들을 다 제거한다. 이어져있는 node의 indegree를 1씩 줄이면서 나타낼 수 있다.

이어져 있는 노드를 가리키는 노드가 더이상 없을 때, que에 집어넣는다.

n번을 다 돌때까지 queue가 비지 않는다면 true이다.

bool topology_sort(vector<vector<int>>& di, vector<int>& indegree){
    queue<int> que;
    que.push(0);
    
    for(int i=0; i<di.size(); i++){
        if(que.empty()) return false; // cycle 발생
        
        int room = que.front(); que.pop();
        for(auto to : di[room]){
            if(--indegree[to] == 0) que.push(to);
        }
    }
    return true;
}