[BOJ 백준] 16947번 서울 지하철 2호선

문제

BOJ 16947 : https://www.acmicpc.net/problem/16947

16947번: 서울 지하철 2호선

접근

BFS 혹은 DFS로 구현할 수 있다. 나는 DFS를 이용하여 문제를 해결해 보았다.

먼저 입력으로 들어오는 노선도는 간선의 개수와 정점의 개수가 같은 연결그래프라고 주어진다. 따라서 사이클(cycle)이 하나만 나오는 연결그래프임을 알 수 있다. 따라서 DFS를 이용하여 사이클을 먼저 찾아주어 배열에 표시해두었다.

다음으로 모든 정점에 대해 순환선(사이클)과의 거리를 DFS로 탐색하여 출력해준다.

 

코드

// algorithm study
// BOJ_16947_서울 지하철 2호선

#include <iostream>
#include <vector>

using namespace std;

vector<int> sub[3005];
int n, f = 0, chk = 0, c = 0;
int visit[3005] = {0}, sub_l[3005] = {0};

void dfs_cycle(int n) {
    if (n == f && c > 2) {
        chk = 1;
        return;
    }
    if (visit[n] == 1)
        return;
    visit[n] = 1;
    for (int i = 0; i < sub[n].size(); i++) {
        c++;
        dfs_cycle(sub[n][i]);
        if (chk == 1)
            return;
        c--;
    }
    visit[n] = 0;
}

void dfs(int n, int b) {
    if (visit[n] == 1) {
        sub_l[f] = c;
        return;
    }
    for (int i = 0; i < sub[n].size(); i++) {
        if (sub[n][i] == b)
            continue;
        c++;
        dfs(sub[n][i], n);
        if (sub_l[f] > 0)
            return;
        c--;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        sub[a].push_back(b);
        sub[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        f = i;
        c = 0;
        dfs_cycle(i);
        if (chk == 1)
            break;
    }
    for (int i = 1; i <= n; i++) {
        if (visit[i] == 1)
            cout << 0 << " ";
        else {
            c = 0;
            f = i;
            dfs(i, i);
            cout << sub_l[i] << " ";
        }
    }
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study