백준 16947 서울 지하철 2호선

문제 링크

역의 개수가 3000이다. 크지 않기 때문에 모든 노드에 대해서 DFS를 돌리더라도 $O(N^2)$이므로 시간 초과가 나지 않는다.

DFS를 2번 돌렸다.

DFS 1 : 특정 노드가 cycle인지

DFS 탐색 도중에 시작 노드를 다시 만나는지 확인을 했다. 모든 간선은 양방향 간선이므로 모든 노드가 cycle로 판단되면 안되기에 이전에 방문한 노드는 방문하지 않도록 했다.

void DFS(int startNode, int beforNode, int curNode){
    isVisited[curNode] = true;
    if(curNode == startNode){
        if(startFlag){
            startFlag = false;
            isVisited[curNode] = false; // 시작 노드를 재 방문할 수 있도록
        }else{
            isCycle[curNode] = true;
            findFlag = true;
            return;
        }
    }
    for(auto nextNode : nextNodes[curNode]){
        if(isVisited[nextNode] || nextNode == beforNode) continue;
        DFS(startNode, curNode, nextNode);
        if(findFlag) return;
    }
}

DFS 2 : 간선 까지의 거리가 몇인지

입력은 간선까지 거리를 구할 수 있는 경우만 주어진다. 더 이상 갈 곳이 없는 경로와 언젠가는 cycle을 만나는 경우로 나뉜다.

int distDFS(int dist, int node){
    isVisited[node] = true;
    if(isCycle[node]) return dist;
    for(auto nextNode : nextNodes[node]){
        if(isVisited[nextNode]) continue;
        int curDist = distDFS(dist + 1, nextNode);
        if(curDist != 0) return curDist;
    }
    return 0; // 더이상 갈 곳이 없는 경우
}

전체 코드

#include<iostream>
#include<vector>

using namespace std;

bool isCycle[3001];
bool isVisited[3001];
int dist[3001]; // 노드 - 순환선 거리
int N;
bool startFlag;
bool findFlag;

vector<vector<int>> nextNodes(3001);

void DFS(int startNode, int beforNode, int curNode){
    isVisited[curNode] = true;
    if(curNode == startNode){
        if(startFlag){
            startFlag = false;
            isVisited[curNode] = false; // 시작 노드를 재 방문할 수 있도록
        }else{
            isCycle[curNode] = true;
            findFlag = true;
            return;
        }
    }
    for(auto nextNode : nextNodes[curNode]){
        if(isVisited[nextNode] || nextNode == beforNode) continue;
        DFS(startNode, curNode, nextNode);
        if(findFlag) return;
    }
}

int distDFS(int dist, int node){
    isVisited[node] = true;
    if(isCycle[node]) return dist;
    for(auto nextNode : nextNodes[node]){
        if(isVisited[nextNode]) continue;
        int curDist = distDFS(dist + 1, nextNode);
        if(curDist != 0) return curDist;
    }
    return 0;
}

void initVisited(){
    for(int i = 1; i <= N;i++){
        isVisited[i] = false;
    }
}

int main(){
    cin >> N;
    for(int i = 0; i < N;i++){
        int left, right;
        cin >> left >> right;
        nextNodes[left].push_back(right);
        nextNodes[right].push_back(left);
    }
    for(int i = 1;i <= N;i++){
        startFlag = true;
        findFlag = false;
        DFS(i, 0, i);
        initVisited();
    }

    for(int i = 1;i <= N;i++){
        dist[i] = distDFS(0, i);
        initVisited();
    }

    for(int i = 1;i<=N;i++){
        cout << dist[i] << " "; 
    }
    cout << "\n";
    
    return 0;
}