BOJ 16947번: 서울 지하철 2호선

문제

문제 바로가기> BOJ 16947번: 서울 지하철 2호선

16947번: 서울 지하철 2호선

 

풀이

1. dfs를 이용해 cycle을 구해준다. 

    이전 노드가 아닌, 다른 노드에서 방문한 노드를 재방문 하는 경우, cycle이라고 볼 수 있다!

2. bfs를 이용해 역과 순환선 사이의 거리를 구해준다!

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

struct QUEUE{ int n, d; };

int N;
bool isFind; // cycle을 찾았는지
int pre[MAX]; // 이전 역
int dist[MAX]; // 순환선과의 거리
bool cycle[MAX]; // 순환선 여부
bool visited[MAX];
vector<int> station[MAX];

void input(){
    cin >> N;
    for (int i = 0; i < N; i++){
        int a, b;
        cin >> a >> b;
        station[a].push_back(b);
        station[b].push_back(a); // 양방향
    }
}

void find_cycle(int cur){
    visited[cur] = true;
    for(int nxt : station[cur]){
        if(isFind) return;
        if(visited[nxt]){
            if(nxt != pre[cur]){ // cycle을 찾은 경우
                isFind = true;
                cycle[cur] = true;

                int tmp = cur;
                while (tmp != nxt){ // cycle 역 추적
                    cycle[pre[tmp]] = true;
                    tmp = pre[tmp];
                }
            }
        }
        else{
            pre[nxt] = cur;
            find_cycle(nxt);
        }
    }
}

void get_dist(){

    // 1. 초기화
    memset(visited, false, sizeof(visited));

    // 2. 시작점 처리
    queue<QUEUE> q;
    for (int n = 1; n <= N; n++){
        if(cycle[n]) {
            visited[n] = true;
            q.push((QUEUE){n, 0});
        }
    }

    // 3. bfs
    while (!q.empty()){
        int n = q.front().n;
        int d = q.front().d;
        q.pop();

        for(int nxt : station[n]){
            if(visited[nxt]) continue;
            visited[nxt] = true;
            q.push((QUEUE){nxt, d + 1});
            dist[nxt] = d + 1;
        }
    }
}

void output(){
    for (int n = 1; n <= N; n++)
        cout << dist[n] << " ";
}

void solve(){
    
    // 1. 순환 노선 찾기
    find_cycle(1);

    // 2. n번 역과 순환선 사이 거리 구하기
    get_dist();

    // 3. n번 역과 순환선 사이 거리 출력
    output();
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    // freopen("../test/input.txt", "r", stdin);
    input();
    solve();
}