[baekjoon] 16947

서울 지하철 2호선

문제

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

 

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

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

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

입력

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

출력

 

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

풀이

한 지점(A)으로부터 DFS로 탐색을 하다가 두번 방문한 지하철역(B)을 발생하면 사이클이 생긴 것이다.

A에서 B까지 가는데 지나친 역들이 모두 사이클에 포함되는 지하철역이 된다.

하지만 이때 아래 같은 그림의 경우 1 2 4 3 순으로 방문하게 되고 4번째 이동에서 사이클을 발견하게 된다.

하지만 지하철역 4는 사이클에 포함되지 않기 때문에 오류가 발생한다.

그렇기 때문에 사이클을 발견하지못하면 해당 지하철역을 삭제해준다.

순환선을 모두 발견했으면 순환선들을 q에 넣고 BFS를 해줘서 답을 구한다.

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>

#define MAX 3001
using namespace std;


vector<int> subway[MAX];
int visitedSubway[MAX];
int answer[MAX];
bool isCycle[MAX];
int n, idx, to;


void input(){
    cin >> n;
    int a, b;
    for(int i = 0; i < n; i++){
        cin >> a >> b;
        subway[a].push_back(b);
        subway[b].push_back(a);
    }
}
int searchCycle(int cv, int prev){
    visitedSubway[idx++] = cv;
    answer[cv] = true;
    int thisIdx = idx;
    for(auto nv : subway[cv]){
        if(nv == prev)continue;
        //사이클 발견, 사이클 시작 지점의 지하철역 반환
        if(answer[nv] != -1){
            return nv;
        }
        int from = searchCycle(nv, cv);
        if(from == -1)continue;
        else {
            //to : 탐색한 지하철역들 중 사이클의 끝 기록
            if(to == 0)to = thisIdx + 1;
            return from;
        }
    }
    //끝일시 idx 감소 = 삭제 효과
    idx--;
    return -1;
}
void addCycleList(int fromNumber){
    bool check = false;
    //사이클 시작 지점 : from 부터 사이클의 끝 to까지 true
    for(int i = 0; i < to; i++){
        if(visitedSubway[i] == fromNumber)check = true;
        isCycle[visitedSubway[i]] = check;
    }
}
void bfs(){
    memset(answer, -1, sizeof(answer));
    queue<int> q; // subwayNumber

    //사이클에 포함된 지하철역들을 q에 추가
    for(int i = 1; i <= n; i++){
        if(isCycle[i]){
            answer[i] = 0;
            q.push(i);
        }
    }
    while(!q.empty()){
        int now = q.front();
        q.pop();

        for(auto i : subway[now]){
            if(answer[i] != -1)continue;
            else answer[i] = answer[now] + 1;
            //현재 지하철역이 사이클에 포함된 경우 거리를 0으로 초기화하고 push
            q.push(i);
        }
    }
    
}

void solve(){
    input();
    memset(answer, -1, sizeof(answer));
    int fromNumber = searchCycle(1, -1);
    addCycleList(fromNumber);
    bfs();
    for(int i = 1; i <= n; i++)cout << answer[i] << " ";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();
}