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

백준의 서울 지하철 2호선(16947) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 모든 역에서 순환선과의 거리를 구해야 하기 때문에 먼저 어떤 역이 순환선에 속해있는지 부터 찾아줘야 한다.

   순환선에 속해있는지 판단하는 부분을 본인은 깊이우선탐색(DFS) 법으로 구현해 보았다.

   현재역에서 연결된 역의 가장 깊은 곳 까지 들어가 봤을 때, 자기자신이 다시 나오게 되면 이는 순환선이라는 것을

   의미하게 된다.

   DFS를 구현할 때 조심해야 할 부분은 '갔다가 바로 돌아오는 것'은 순환선이 아니라는 점이다.

   바로 이런 경우이다.

  

   이렇게 생긴 역이 있다고 가정해보자. 이 때, 1번 역이 순환선인지 판단하기 위해서 DFS를 호출하게 되면,

   2번 역을 호출하게 될 것이고, 2번역에서 또 바로 1번 역을 호출하는 경우가 발생할 수가 있다.

   이렇게 되면, 1번 역에서 출발해서 다시 1번 역으로 돌아왔기 때문에 순환선이 아님에도 순환선으로 잘못 판단할 수

   있게 된다. "그러면 방문한 역을 다시 방문 못하게 하면 되잖아요 ?!" 그렇게 되면 다시 시작점으로 돌아올 수가 없다.

   따라서 위의 말 처럼 구현할 경우 모든 역이 순환선이 아니라고 판단될 수가 있다.

   그래서 본인은 다음과 같이 구현해 보았다.

void DFS(int Cur, int Start, int line)    // 순환선인지 판단하기 위한 DFS 함수. (현재 역, 시작 역, 경로의 수)
{
    if (Cur == Start && line >= 2)     // 단순히, 현재역 = 시작역일 때 종료시키는 것이 아니라
    {                              // 위의 문제점을 해결하기 위해, 최소 2개 이상의 경로를 지난 경우
        Cycle = true;                // 순환선이라고 체크해주기.
        return;
    }

    Visit[Cur] = true;                // 방문표시
    for (int i = 0; i < Station[Cur].size(); i++) // 현재 역과 연결된 모든 역을 탐색해보면서
    {
        int Next = Station[Cur][i];
        if (Visit[Next] == false)            // 아직 탐색하지 않은 역이라면...
        {
            DFS(Next, Start, line + 1);      // 탐색 시작.
        }
        else                             // 이미 탐색한 역이라면
        {
            if (Next == Start && line >= 2)  // 시작점과 같으면서, 2개 이상의 경로를 지났을 때만
            {
                DFS(Next, Start, line);     // 호출
            }
        }

        if (Cycle == true) return;
    }
}

2) 위의 과정을 통해서 어떤 역이 순환선에 속해 있는 역인지는 알게 되었다.

   이제는 모든 역을 탐색하면서 가장 가까운 순환선과의 거리만 확인하면 된다.

   본인은 이 부분을 BFS를 통해서 구현해 보았다. 탐색 과정에서, 순환선에 속해있는 역을 만나게 되면 바로 거리를

   반환시키고 종료하도록 구현하였다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 3000 + 1
using namespace std;
 
int N;
bool Cycle;
bool Visit[MAX];
bool Check_Cycle_Station[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 DFS(int Cur, int Start, int line)
{
    if (Cur == Start && line >= 2)
    {
        Cycle = true;
        return;
    }
 
    Visit[Cur] = true;
    for (int i = 0; i < Station[Cur].size(); i++)
    {
        int Next = Station[Cur][i];
        if (Visit[Next] == false)
        {
            DFS(Next, Start, line + 1);
        }
        else
        {
            if (Next == Start && line >= 2)
            {
                DFS(Next, Start, line);
            }
        }
 
        if (Cycle == true) return;
    }
}
 
int BFS(int a)
{
    memset(Visit, false, sizeof(Visit));
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, 0));
    Visit[a] = true;
 
    while (Q.empty() == 0)
    {
        int Cur = Q.front().first;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (Check_Cycle_Station[Cur] == true) return Cnt;
 
        for (int i = 0; i < Station[Cur].size(); i++)
        {
            int Next = Station[Cur][i];
            if (Visit[Next] == false)
            {
                Visit[Next] = true;
                Q.push(make_pair(Next, Cnt + 1));
            }
        }
    }
}
 
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        memset(Visit, false, sizeof(Visit));
        Cycle = false;
 
        int Start_Station = i;
        DFS(i, Start_Station, 0);
 
        if (Cycle == true)
        {
            Check_Cycle_Station[i] = true;
        }
    }
 
    vector<int> Answer;
    for (int i = 1; i <= N; i++)
    {
        if (Check_Cycle_Station[i] == true)
        {
            Answer.push_back(0);
            continue;
        }
 
        Answer.push_back(BFS(i));
    }
 
    for (int i = 0; i < Answer.size(); i++)
    {
        cout << Answer[i] << " ";
    }
    cout << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}