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

문제 링크 : www.acmicpc.net/problem/16947

16947번: 서울 지하철 2호선

사이클이 나오는 지점을 찾으면 되는 문제이다.

문제풀이는 다음과 같다.

 

1. 양방향 간선을 모두 입력 받는다.

2. int형 인자를 2개 넘겨받는 int형 함수 go를 만든다. 코드는 다음과 같다.

int go(int x, int p){ // 현재 노드, 직전 방문 노드
    if(check[x]==1) return x; // 방문한 적이 있는 노드라면 해당 노드를 반환
    check[x] = 1;
    for(auto y : a[x]){
        if(y==p) continue; // 2개의 노드로 사이클이 만들어지는 것을 방지하기 위함
        int res = go(y,x);
        if(res==-2) return -2; // 사이클에 포함이 안되는 편도라인
        if(res>=1){
            check[x] = 2;
            if(x==res) return -2; // 사이클의 출발지점과 동일하다는 의미
            else return res; // 이미 방문한 사이클
        }
    }
    return -1; // 탐색 종료. 즉, 양방향이 아닌 편도의 끝에 도달
}
// -2 : 사이클을 이미 찾았으며, 사이클에 포함되지 않음
// -1 : 사이클을 못찾음

3. 탐색 종료후 int main()함수 내에서 아래와 같이 큐를 만들고 거리를 계산하는 식을 세운다.

    queue<int> q;
    for(int i=1; i<=n; i++){
        if(check[i]==2){ // 사이클
            dist[i] = 0;
            q.push(i); // 사이클은 큐에 넣어주자.
        }
        else dist[i] = -1; 
    }
    while(!q.empty()){
        int x = q.front(); q.pop();
        for(auto y:a[x]){ // 사이클과 연결되어있으면 거리는 +1이 되고
            if(dist[y]==-1){
                q.push(y);
                dist[y] = dist[x]+1; // 연결되어있는 선으로 파고들어서 계속 +1씩 추가해주는 원리
            }
        }
    }

#include <iostream>
#include <vector>
#include <queue>
#define MAX 3001
using namespace std;

vector<int> a[MAX];
int check[MAX], dist[MAX]; // check = 0 = not visitied, 1 = visited, 2 = cycle

int go(int x, int p){
    if(check[x]==1) return x;
    check[x] = 1;
    for(auto y : a[x]){
        if(y==p) continue;
        int res = go(y,x);
        if(res==-2) return -2; // 사이클에 포함이 안되는 편도라인
        if(res>=1){
            check[x] = 2;
            if(x==res) return -2; // 사이클의 출발지점과 동일하다는 의미
            else return res; // 이미 방문한 사이클
        }
    }
    return -1; // 탐색 종료. 즉, 양방향이 아닌 편도의 끝에 도달.
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,u,v;
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    go(1,-1);
    queue<int> q;
    for(int i=1; i<=n; i++){
        if(check[i]==2){
            dist[i] = 0;
            q.push(i);
        }
        else dist[i] = -1;
    }
    while(!q.empty()){
        int x = q.front(); q.pop();
        for(auto y:a[x]){
            if(dist[y]==-1){
                q.push(y);
                dist[y] = dist[x]+1;
            }
        }
    }
    for(int i=1; i<=n; i++) cout << dist[i] << " ";
    cout << "\n";
    return 0;
}