(2024-11-01) 1 문제 : 백준 - 1103 (서울 지하철 2호선)

 

이 문제는 먼저 사이클을 탐색하고, 그 사이클로부터 각 정점의 거리를 구하는 문제이다.

먼저, 사이클을 구하기 위해선 이전의 노드를 기록할 필요가 있다.

 

일반적으로 DFS를 통해 경로를 탐색할 때 방문체크 배열을 통해 한 번 진입한 곳은 다시 진입하지 않도록 하는데, 사이클은 반대로 한 번 진입한 적이 있던 노드에서 탐색될 수 밖에 없다. 그러므로 방문체크를 할 때, 방문한 적이 있다면 이 노드가 사이클에 속하는 노드인지 검사하는 작업을 추가로 수행해야 한다.

 

그렇다면 사이클은 어떻게 판단할까? 경로를 탐색할 때 직전에 탐색했던 노드를 기록하는 것이다. DFS는 방문체크를 보퉁 2가지의 방법으로 한다. DFS를 탈출할 때 방문체크를 false로 만들어 다시 진입할 수 있도록 하는 방법과 false로 만들지 않아 다시 진입할 수 없도록 하는 방법이다.

 

전자는 가능한 모든 경우의 수를 탐색할 때 사용하고, 후자는 모든 노드를 탐색하기 위해 사용을 한다. 만약 전자의 방식으로 방문체크를 해줬다면 다음 노드의 방문체크가 true인 경우는 현재 탐색중인 경로에 다음 노드가 포함되는 경우밖에 없다.

 

즉, 1-> 2-> 3-> 4 의 순서로 경로를 탐색하고 있다면 (1, 2, 3, 4)만 다음 노드가 true일 것이다. 즉 다음 노드의 방문체크가 true라면 사이클이 발생했다고 판단할 수 있다. 하지만 한 가지 예외 경우가 있다. 바로 다음 노드가 직전에 탐색한 노드인 경우이다. 이 문제는 간선이 양방향으로 되어있기 때문에 경로에 반대 방향의 경로가 포함되어 있다.

 

즉, 정상적으로 간다면 1->2->3->4 의 경로만 가야 하는데, 1->2->3 까지 갔다가 갑자기 역행해서 1->2->3->2->3의 방식으로 움직일 수도 있다는 것이다. 이를 방지하기 위해 우리는 방문체크를 한 것이기도 하다.

 

그러므로, dfs를 할 때 바로 직전의 노드를 배열에 기록해뒀다가 다음에 진입할 노드가 이전의 노드는 아니지만 방문체크는 true로 되어있다면 사이클이 발생했다고 판단할 수 있는 것이다.

 

사이클을 찾았다면 배열에 기록된 이전 노드를 쭉 타고가면서 사이클 노드를 모두 걸러주면 된다. 사이클 노드를 모두 감지했다면 BFS를 통해 각 사이클 노드로부터 역까지의 거리를 구하면 된다.

 

모든 사이클 노드를 Queue에 넣고 거리를 구해줘도 되지만, 나는 하나의 노드만 넣고 다음 위치가 사이클 노드라면 거리를 증가시키지 않고 사이클 노드가 아니라면 거리를 증가하는 식으로 거리를 구해주었다.

 

#include <iostream>
#include <vector>
#include <queue>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int NumVertex = 0;
int StartIndex = 0;

std::vector<bool> isVisit;
std::vector<bool> isCycle;
std::vector<std::vector<int>> Link;

void MakeCycle(std::vector<int>& _PrevVertex, int _StartIndex)
{
    isCycle[_StartIndex] = true;
    StartIndex = _StartIndex;

    int CurIndex = _PrevVertex[_StartIndex];

    while (CurIndex != _StartIndex)
    {
        isCycle[CurIndex] = true;
        CurIndex = _PrevVertex[CurIndex];
    }
}

void FindCycle(int _Vertex)
{
    static bool isFind = false;
    static std::vector<int> PrevVertex(NumVertex);

    isVisit[_Vertex] = true;

    for (int i = 0; i < Link[_Vertex].size(); i++)
    {
        if (isFind == true)
        {
            return;
        }

        int NextVertex = Link[_Vertex][i];

        if (isVisit[NextVertex] == true)
        {
            if (PrevVertex[_Vertex] != NextVertex)
            {
                PrevVertex[NextVertex] = _Vertex;
                isFind = true;

                MakeCycle(PrevVertex, _Vertex);

                return;
            }

            continue;
        }

        PrevVertex[NextVertex] = _Vertex;
        FindCycle(NextVertex);
    }

    isVisit[_Vertex] = false;
}

int main()
{
    Init();
    
    std::cin >> NumVertex;

    isVisit.resize(NumVertex);
    isCycle.resize(NumVertex);
    Link.resize(NumVertex);

    for (int i = 0; i < NumVertex; i++)
    {
        int Start = 0, End = 0;
        std::cin >> Start >> End;

        Link[Start - 1].push_back(End - 1);
        Link[End - 1].push_back(Start - 1);
    }

    FindCycle(0);

    std::vector<int> MinDistToCycle(NumVertex);
    std::fill(isVisit.begin(), isVisit.end(), false);

    std::queue<std::pair<int, int>> BFS;
    BFS.push({ StartIndex, 0 });
    isVisit[StartIndex] = true;

    while (BFS.size() > 0)
    {
        auto [CurIndex, Dist] = BFS.front();
        BFS.pop();
        
        for (int i = 0; i < Link[CurIndex].size(); i++)
        {
            int NextNode = Link[CurIndex][i];

            if (isVisit[NextNode] == true)
            {
                continue;
            }

            int NextDist = Dist;
            isVisit[NextNode] = true;
            
            if (isCycle[NextNode] == false)
            {
                NextDist++;
                MinDistToCycle[NextNode] = NextDist;
            }

            BFS.push({ NextNode, NextDist });
        }
    }

    for (int Answer : MinDistToCycle)
    {
        std::cout << Answer << " ";
    }

    return 0;
}