[백준] 2252 줄 세우기 : C++ 풀이

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

2252번: 줄 세우기

 

위상정렬을 활용하는 문제입니다.

 

단순히 위상정렬을 구현하면 되는 문제인데, 개념이 생소해서 많이 헷갈릴거라 봅니다.

본인 역시 단순히 배열을 통해 방향 그래프를 구현하여 문제를 해결하면 되는가 싶었지만 아니였습니다.

 

제 개인적으로 헷갈릴만한 점 몇개를 요약하고 코드를 포스트하였습니다.

 

 

1. 1부터 N까지 노드가 있을 때, 각각의 노드가 출력되기 이전에 출력되어야할 값은 반드시 하나가 아니라 여러개일 수도 있습니다.

 

그렇게 될 경우 단순 배열로 풀기에는 어렵고, 그래프를 이용해야한다는 것임을 알 수 있습니다.

 

 

 

2. 그래프로 구현을 할 때, 단순히 방향그래프로 그리기 보다는 해당 노드가 출력되기 위해 우선적으로 출력되어야할 노드를 담아두었습니다.

 

그렇게하면 vector를 따라가며 방문을 했는지 체크가 가능해집니다.

또한 이런 방식을 미루어보아 DFS가 최적이라고 판단하였습니다.

 

아래는 코드입니다.

 

감사합니다.

 

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

vector<int> topology[32001];
bool visit[32001];

void dfs(int node){
    if(visit[node]) return;
    for(int i : topology[node]) {
        if(!visit[i]) {
            dfs(i);
        }
    }
    visit[node] = true;
    cout<<node<<' ';
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N, M; cin>>N>>M;
    for(int i=0; i<M; ++i) {
        int tmp1, tmp2; cin>>tmp1>>tmp2;
        topology[tmp2].push_back(tmp1); // tmp2가 출력되기 위해선, tmp1 이 방문상태이어야한다.
    }
    queue<int> q;
    for(int i=1; i<=N; ++i) {
        if(topology[i].empty()) {
           visit[i] = true;
           cout<<i<<" ";
        }
        else q.push(i);
    }
    while(!q.empty()) {
        int node = q.front(); q.pop();
        if(visit[node]) continue;
        else dfs(node);
    }
}