백준 16947 - 서울 지하철 2호선 (C++)

문제

• 문제 링크

  
   BOJ 16947 - 서울 지하철 2호선 
  

• 문제 요약

$N$개의 정점과 간선으로 이루어진 그래프가 주어진다.
임의의 두 역 사이에 경로가 항상 존재할 때, 각 노드로부터 사이클 형상 까지의 거리를 구해보자.

• 제한

TL : $2$ sec, ML : $512$ MB




$3 ≤ N ≤ 3,000$

알고리즘 분류

• 그래프 이론(graphs)
• 그래프 탐색(graph_traversal)
• 깊이 우선 탐색(dfs)
• 너비 우선 탐색(bfs)

풀이

   $N$개의 간선으로 이루어진 그래프에서 사이클을 떼네어볼 수 있는가를 묻는 교육적인 문제이다.
나는 개인적으로 indegree를 이용한 bfs를 이용해 사이클을 분리하는 방식을 선호한다.
다음의 과정을 보자.

1. 간선 정보를 입력 받으면서 indegree를 카운트 해주면, 리프 노드는 indegree가 $1$인 노드들이다.
2. 리프 노드들로부터 bfs를 시작하자. 이때 마주치는 인접 노드들마다 indegree를 감소 시켜 주고 $1$이 됐다면 큐에 넣자.
3. 위 과정에서 방문하게 되는 노드들마다 표시를 해두고 나면, 최종적으로 사이클에 속한 노드들을 제외한 모든 노드들에 표시가 완료된다.

이제 우리는 그래프를 다음과 같이 새로운 시선으로 바라 볼 수 있다.

"사이클에 속한 정점들을 루트로 하는 $k$개의 트리"

각 $k_i$의 정점으로부터 하위 노드로의 탐색으로 문제의 정답을 모두 채워줄 수 있다.

전체 코드

#include<bits/stdc++.h>
#define N 3001
using namespace std;
 
vector <int> Gr[N];
int n, C[N], Cy[N], W[N];
 
void f()
{
    queue <int> Q;
    for (int i(1); i <= n; i++)
        if (C[i] == 1)
            Cy[i] = 1, Q.push(i);
    while (Q.size())
    {
        int x(Q.front()); Q.pop();
        for (int i : Gr[x])
            if (--C[i] == 1 && !Cy[i])
                Cy[i] = 1, Q.push(i);
    }
}
void f(int p, int q, int w)
{
    for (int i : Gr[p])
        if (i ^ q && Cy[i])
            W[i] = w, f(i, p, w + 1);
}
int main()
{
    cin >> n;
    for (int o{}, i, j; o++ < n; C[i]++, C[j]++)
        scanf("%d %d", &i, &j), Gr[i].push_back(j), Gr[j].push_back(i);
    f();
    for (int i(1); i <= n; i++)
        if (!Cy[i])
            f(i, i, 1);
    for (int i(1); i <= n; printf("%d ", W[i++]));
}

comment

끝