[Algorithm]Baekjoon 2252번 : 줄 세우기

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

2252번: 줄 세우기

using namespace std;
 
int n, m, a, b;
bool visited[32001] = { false };
vector<vector<int>> graph(32001);
 
void DFS(int node)
{
    for (int i = 0; i < graph[node].size(); ++i)
    {
        int child = graph[node][i];
 
        if (visited[child]) continue;
        visited[child] = true;
        DFS(child);
    }
 
    printf("%d ", node);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < m; ++i)
    {
        cin >> a >> b;
        
        graph[b].push_back(a);
    }
 
    for (int i = 1; i <= n; ++i)
    {
        if (visited[i]) continue;
        visited[i] = true;
        DFS(i);
    }
}
 
 
 
 

 

우선순위를 따져서 순서를 출력해야하는 문제. 나는 최근에 DFS풀이를 더 많이했어서 그런지, 바로 위 코드가 떠올라서 제출해서 통과했다. 근데 BFS로들 더 많이 풀긴하는 것 같았다. (딱히 상관없는 것 같다.)

 

입력값에 비교횟수 m과 해당 횟수만큼 숫자 두개씩 주어진다.

1 3 이 주어지면 1번이 3번보다 앞에 있어야 한다는 의미이다. 

그래서 나는 상속관계로 표현해봤다. 3이 뒤에있어야 하니, 3을 부모노드로 생각하고 3보다 앞에와야하는 1을 3의 자식노드로 넣었다.

이후, 그냥 1번노드부터 방문검사 후, DFS를 수행한다. DFS는 리프노드까지 먼저 파고든 후 거기서부터 숫자를 출력하면 된다. 자식노드들을 타고 쭉쭉내려가서 출력 후, 전부 끝나서 되돌아온 다음에야 자기자신을 출력한다.

 

즉 n은 3이고 m은 2, 그리고 (1, 3), (2, 3)이 주어진다고 가정했을 때 부모노드는 3이고 자식노드는 각각 1,2일 것이다.

먼저 1번노드에 대한 탐색을 시도한다. 자식노드가 없으니 그냥 탐색표시하고 자기를 출력하고 끝낸다.

2번노드도 마찬가지.

3번노드는 자식 1,2가 있지만 이미 이전에 방문했었기 때문에 해당 for문을 바로 끝내고 자기자신을 출력하고 끝낸다.

 

코드가 워낙 간단해서 보면 바로 이해가능..