[Algorithm]Baekjoon 16947번 :: 서울 지하철 2호선

https://www.acmicpc.net/problem/16947

16947번: 서울 지하철 2호선

 

struct Node
{
    int node;
    int distance;
};
 
int n, a, b;
bool isNodeInCycle[3001] = { false };
int nodeDistances[3001] = { 0 };
vector<vector<int>> graph(3001);
 
 
bool DFS(int start, int node, int distance)
{
    isNodeInCycle[node] = true;
 
    for (int i = 0; i < graph[node].size(); ++i)
    {
        int nextNode = graph[node][i];
 
        if (distance >= 2 && nextNode == start) return true;
        else if (!isNodeInCycle[nextNode])
        {
            if (DFS(start, nextNode, distance + 1)) return true;
        }
    }
 
    isNodeInCycle[node] = false;
    return false;
}
 
void BFS()
{
    queue<Node> q;
    bool visited[3001];
    memcpy(visited, isNodeInCycle, 3001);
 
    for (int i = 1; i <= n; ++i)
    {
        if (!isNodeInCycle[i]) continue;
        visited[i] = true;
        q.push({ i,0 });
    }
 
    while (!q.empty())
    {
        int curNode = q.front().node;
        int curDistance = q.front().distance;
        q.pop();
 
        for (int i = 0; i < graph[curNode].size(); ++i)
        {
            int nextNode = graph[curNode][i];
            int nextDistance = curDistance + 1;
 
            if (visited[nextNode]) continue;
            visited[nextNode] = true;
            nodeDistances[nextNode] = nextDistance;
            q.push({ nextNode,nextDistance });
        }
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> a >> b;
 
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
 
    for (int i = 1; i <= n; ++i)
    {
        DFS(i, i, 0);
        if (isNodeInCycle[i]) break;
    }
 
    BFS();
 
    for (int i = 1; i <= n; ++i)
    {
        cout << nodeDistances[i] << ' ';
    }
}

 

주어진 간선의 정보를 토대로 그래프를 만들고, 해당 그래프에서 싸이클인 노드들을 찾아야하는 문제이다.

문제에서 요구하는 정답은 순환이 아닌것 노드들이 순환역에서 얼마나 떨어져있는지를 출력해야하는 문제이기 때문에, 일단 순환에 속해있는 노드들을 구하면 그 노드들을 기준으로 bfs를 돌리면 순환 아닌노드들이 얼마나 떨어져있는지 알 수 있다.

 

그러면 순환인것들은 어떻게 찾아야 할까? 

각 정점을 기준으로 백트래킹을 돌릴것인데, 돌릴때 맨 처음 시작노드를 기준(start)로 잡은다음에 하위노드들로 쭉쭉 뻗어 나간다. 그러다가 start를 만났으면서, 거리가 2이상일 때 사이클로 판별한다. 거리제한이 있는 이유는 노드가 양방향이라서 자식에서 다시 바로 부모로 올라가는 경우가 있기 때문이다.

그러면 사이클인 노드들을 찾았으니, 이 노드들 기준으로 BFS 수행해서 문제에서 요구하는 값을 구하면 된다.

 

근데 이렇게 풀이 시, 68ms정도의 수행속도가 나왔다.

지금 위코드같은 경우는, 노드1부터 n까지 DFS돌리다가 사이클인거 찾으면 바로 빠져나오게 했는데, 그 말은 순환인 정점들이 n값에 가까울수록 DFS수행을 더 해야한다는 것이다. 

 

근데 다른사람들의 풀이 수행속도를 보면 0ms도 있다. 어느 노드에서 시작하든, 해당 노드를 기준으로하는 한번의 DFS로 끝난다.

대신 부모 자식간의 관계를 계속 저장해나가야 한다. 그래야 싸이클을 발견했을 때 부모자식정보를 토대로 역으로 되돌아가면서 순환이라고 체크해줄 수 있기 때문이다.

어쨌든 그저 연결된 노드를 타고 내려가다가 '방문한 적 있으면서 부모가 아닌 노드'를 발견 했을 때 싸이클이 발생했다고 판단하고 모든 탐색을 중지한다. 중지하기전에 말했듯이 부모노드정보를 역으로 타고 올라가면서 순환인 노드라고 다 체크해줘야 한다.

 

그래서 다시 작성해본 코드는 아래와 같다.

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
 
using namespace std;
 
 
struct Node
{
    int node;
    int distance;
};
 
int n, a, b;
bool visited[3001] = { false };
bool cycledNodes[3001] = { false };
int nodeDistances[3001] = { 0 };
int parents[3001] = { 0 };
bool isDetectedCycle = false;
vector<vector<int>> graph(3001);
 
void DFS(int curNode)
{
    visited[curNode] = true;
 
    for (int i = 0; i < graph[curNode].size(); ++i)
    {
        if (isDetectedCycle) return;
 
        int nextNode = graph[curNode][i];
 
        if (visited[nextNode]) 
        {
            if (nextNode != parents[curNode]) // 싸이클발견.
            {
                isDetectedCycle = true;
                cycledNodes[curNode] = true;
                int parent = parents[curNode];
 
                while (parent != nextNode)
                {
                    cycledNodes[parent] = true;
                    parent = parents[parent];
                }
                cycledNodes[parent] = true;
 
                return;
            }
        }
        else
        {
            parents[nextNode] = curNode;
            DFS(nextNode);
        }
    }
}
 
void BFS()
{
    queue<Node> q;
    bool tempVisited[3001] = { false };
 
    for (int i = 1; i <= n; ++i)
    {
        if (!cycledNodes[i]) continue;
        tempVisited[i] = true;
        q.push({ i,0 });
    }
 
    while (!q.empty())
    {
        int curNode = q.front().node;
        int curDistance = q.front().distance;
        q.pop();
 
        for (int i = 0; i < graph[curNode].size(); ++i)
        {
            int nextNode = graph[curNode][i];
            int nextDistance = curDistance + 1;
 
            if (tempVisited[nextNode]) continue;
            tempVisited[nextNode] = true;
            nodeDistances[nextNode] = nextDistance;
            q.push({ nextNode,nextDistance });
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> a >> b;
 
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
 
    DFS(1);
    BFS();
 
    for (int i = 1; i <= n; ++i)
    {
        cout << nodeDistances[i] << ' ';
    }
}

 

 

한번의 DFS로 싸이클체크와 싸이클을 구성하는 노드들을 찾을 수 있으며, 수행속도는 0ms로 매우 빠르다.