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

문제 링크입니다. https://www.acmicpc.net/problem/16947

16947번: 서울 지하철 2호선

순환되는 그래프를 찾을 수 있는지를 물어보는 문제였습니다.

DFS와 BFS를 함께 써야했던 문제입니다.

그래프가 양방향으로 주어집니다.

주어진 그래프는 순환하는 지점이 만들어지는데, 해당 지점에 속하지 않은 정점과 순환하는 곳과의 거리를 구하는 문제입니다.

 

그렇다면, 2가지를 구해야하는데

1. 순환하는 지점을 구해야한다.

2. 속하지 않는 지점과 순환하는 곳과의 거리를 구해야한다.

 

 

1번 부터 생각해보겠습니다.

X번부터 시작했을 때, X번으로 돌아오면 됩니다.

따라서 DFS를 이용해 깊은 곳까지 들어간 다음, 시작점과 같은 정점이 나오면 순환선에 속한다고 저장하면 됩니다.

 

이때 주의해야할 점이 하나 있는데, 순환하려면 정점을 2개 이상 지나야한다는 것입니다. 따라서 이동횟수를 저장해 2회 이상 방문했는지를 확인해줘야합니다.

void dfs(int start, int x, int cnt){
    if(start == x && cnt >= 2){
        Find = true;
        return;
    }
    check[x] = 1;
    for(int i = 0; i < connect[x].size(); i++){
        int xx = connect[x][i];
        if(check[xx] == 0){
            dfs(start, xx, cnt + 1);
        }
        else if(start == xx && cnt >= 2){
            dfs(start, xx, cnt);
        }
        if(Find) return;
    }

 

이렇게 1~N번 정점까지 DFS를 통해 순환하는 정점을 구할 수 있습니다.

 

순환선에 속하지 않은 정점과 순환선과의 거리를 구할 때는 BFS를 통해 순환선 노드중 하나만 만나게 되면 이동 횟수를 출력하주면 됩니다. 

순환선에 속하는 정점은 거리가 0이니 이를 출력해주면 됩니다.

 

자세한 것은 코드를 참고해주세요

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second

using namespace std;

int N;
vector<int> connect[3001];
int circular_station[3001];
int check[3001];
bool Find = false;

void dfs(int start, int x, int cnt){
    if(start == x && cnt >= 2){
        Find = true;
        return;
    }
    check[x] = 1;
    for(int i = 0; i < connect[x].size(); i++){
        int xx = connect[x][i];
        if(check[xx] == 0){
            dfs(start, xx, cnt + 1);
        }
        else if(start == xx && cnt >= 2){
            dfs(start, xx, cnt);
        }
        if(Find) return;
    }
}

int bfs(int start){
    memset(check, 0, sizeof(check));
    queue<P> q;
    q.push({start, 0});
    check[start] = 1;
    while(!q.empty()){
        int x = q.front().F;
        int cnt = q.front().S;
        q.pop();
        if(circular_station[x] == 1) return cnt;
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i];
            if(check[xx] == 0){
                check[xx] = 1;
                q.push({xx, cnt + 1});
            }
        }
    }
}

void solve(){
    for(int i = 1; i <= N; i++){
        memset(check, 0, sizeof(check));
        Find = false;
        dfs(i, i, 0);
        if(Find){
            circular_station[i] = true;
        }
    }
    for(int i = 1; i <= N; i++){
        if(circular_station[i] == 1) cout << "0" << " ";
        else cout << bfs(i) << " ";
    }
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 1; i <= N; i++){
        int x, y;
        cin >> x >> y;
        connect[x].push_back(y);
        connect[y].push_back(x);
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요