[BAEKJOON] 16947. 서울 지하철 2호선

Posted on February 09, 2021

문제 :

서울 지하철 2호선은 다음과 같이 생겼다.

지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.

두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다.

지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구해보자.

입력 :

첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다.

출력 :

총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, …, N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.

풀이 :

처음에는 어떻게 접근해야할지 고심해야 했던 문제였다.

문제를 해결하기 위한 생각해낸 key point만 먼저 정리해보면,

순환선을 먼저 파악해야한다. → 순환선이 파악되면 순환선에서 뻗어져나가는 트리 형태의 지선은 bfs로 탐색이 가능하다.
순환선을 파악하기 위해선 랜덤의 출발 인덱스에서 dfs 탐색을 실행한다. → 어느 위치에서 시작하더라도 모든 역은 서로 연결되어있기 때문에 순환선을 탐색할 수 있음.
dfs 탐색시에는 바로 직전 노드로 되돌아가는 경우는 순환선이라고 파악할 수 없게 구현해야 한다. → 내가 사용한 방법은 dfs 탐색시 각 노드마다 count를 증가시켜주는 식으로 구현했는데 현재 count보다 1이 적은 직전 노드는 순환이 아니라고 조건문을 걸어주었다.
순환선을 파악했다면 (나는 count를 증가시켜주는 방법을 사용했기 때문에 방문한 노드를 다시 방문한 경우를 count가 -1(초기값)이 아닐 경우로 판단했다.) 정확히 순환선만을 dist 배열 count 값 0으로 바꾸어 준다.

이렇게 dfs 탐색 과정이 끝나면 다시 처음 인덱스부터 마지막 인덱스까지 차례로 dist 값을 확인해보며 값이 0일 경우(순환선의 노드일 경우) bfs 작업과정을 거쳐 나머지 노드의 거리를 측정해준다.

코드 :

코드 보기/접기

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

#define pii pair<int, int>

using namespace std;
vector<vector<int>> adj;
int n, dist[3001];

int DFS(int cur, int cnt) {
    if (dist[cur] != -1) return dist[cur];

    dist[cur] = cnt;
    int size = adj[cur].size();
    for (int k = 0; k < size; k++) {
        if (dist[adj[cur][k]] == cnt - 1) continue;

        int retval = DFS(adj[cur][k], cnt + 1);
        if (retval == dist[cur]) {
            dist[cur] = 0;
            return -2;
        } else if (retval > 0) {
            dist[cur] = 0;
            return retval;
        } else if (retval == -2) {
            dist[cur] = -1;
            return -2;
        }
    }
    dist[cur] = -1;
    return -1;
}

void BFS(int idx) {
    queue<pii > q;
    q.push(pii(idx, 0));

    while (!q.empty()) {
        int cur = q.front().first, curcnt = q.front().second;
        q.pop();

        int size = adj[cur].size();
        for (int k = 0; k < size; k++) {
            int cmp = adj[cur][k];
            if (dist[cmp] != -1) continue;
            dist[cmp] = curcnt + 1;
            q.push(pii(cmp, curcnt + 1));
        }
    }
}

int main() {
    int fir, sec, k;
    cin >> n;
    adj.resize(n + 1);
    fill_n(dist, n + 1, -1);
    for (k = 0; k < n; k++) {
        cin >> fir >> sec;
        adj[fir].push_back(sec);
        adj[sec].push_back(fir);
    }
    DFS(1, 1);
    for (k = 1; k <= n; k++) {
        if (dist[k] == 0) BFS(k);
    }
    for (k = 1; k <= n; k++)
        cout << dist[k] << ' ';
    cout << '\n';
    return 0;
}

Algorithm

algorithm baekjoon C++