[ boj : 16947 ] 서울 지하철 2호선

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

16947번: 서울 지하철 2호선

해설 : 문제자체는 굉장히 간단합니다. n 개의 정점이 주어지고 n 개의 간선이 주어지죠.

입력만으로도 우린 알 수 있어야 합니다. 바로 싸이클이 반드시 1개만 생긴다는 것을요.

 

n 개의 정점이 주어질때 트리가 되기 위한 조건은 n-1개의 간선이 주어져야 되고,

그보다 많은 간선이 주어지면 싸이클이 생기는건 자명하죠.

 

그럼 싸이클을 어떻게 구할 수 있을까요???

 

저는 일단 '스택'을 사용했습니다.

 

1)노드를 방문하면 스택에 담아 놓습니다.

2)만약 방문했던 노드에 또 다시 방문하게 된다면, 방문했던 노드의 번호를 리턴해준 다음 스택에서 top 이 리턴받은 노드와 동일할때까지 pop 해주면서 싸이클에 포함되는 노드들을 체크해줍니다.

3)싸이클에 포함되지 않는 경로로 들어간다면, 빠져나올때마다 스택에서 pop 만 해주면 됩니다.

 

그럼 싸이클을 만들어 놓은 상태이고, 각 정점에서 dfs 를 사용하던 bfs를 사용하던 싸이클까지의 거리를 순차적으로 구해주면 됩니다.

 

저가 여기서 언급하고 싶은건, 싸이클을 확인할 때 제가 했던 방법으로 하지 마세요.

그 이유는 저렇게 하면 리턴 받을때 조건을 확인하고 그에 맞게 처리해야 되는데 저 조건이 굉장히 까다롭습니다.

저렇게 했다가, 싸이클을 확인하고 스택에서 처리를 해줬음에도 불구하고 또 다른 경로로 찾아 들어와 싸이클을 확인해도 싸이클 처리를 중복적으로 처리를 하게 되는 현상이 발생할 수 있더라구요.

 

저 방법 말고 싸이클을 찾는 함수를 void 형으로 선언한 다음에 flag를 하나 선언해서 이 flag를 이용해서 만약 싸이클을 발견했으면 그냥 바로 break 문으로 빠져나오게끔 해주는 것이 깔끔하고 가장 정량화 되어 있는 방법 같습니다.

 

제 코드입니다.(Java)

/**
 * IO Template reference : 류호석
 */

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

import static java.lang.Math.*;

public class Main {
    static FastReader scan = new FastReader();

    static int n;
    static boolean []visit;
    static boolean []cycle;
    static ArrayList<Integer> []adj;
    static Stack<Integer> st = new Stack<>();
    public static void main(String[] args) {
        int t=1;
        //t = scan.nextInt();
        while(t-->0)
            solve();
    }
    static void solve() {
        n=scan.nextInt();
        adj=new ArrayList[n+1];
        visit=new boolean[n+1];
        cycle=new boolean[n+1];
        for(int i=1;i<=n;i++)
            adj[i]=new ArrayList<>();
        int x,y;
        for(int i=0;i<n;i++){
            x= scan.nextInt();
            y=scan.nextInt();
            adj[x].add(y);
            adj[y].add(x);
        }
        find_cycle(1,-1);
        /*for(int i=1;i<=n;i++)
            System.out.print(cycle[i]+" ");
        System.out.println();*/
        for(int i=1;i<=n;i++) {
            //Arrays.fill(visit,false);
            System.out.print(get_ans(i, -1, 0) + " ");
        }
    }
    static int get_ans(int x,int p,int depth){
        if(cycle[x])return depth;
        int ret=(int)1e9;
        for(int u : adj[x]){
            if(u==p)continue;
            ret = min(ret,get_ans(u,x,depth+1));
        }
        return ret;
    }
    static int find_cycle(int s,int p){
        if(visit[s]){
            if(!cycle[s])
                return s;
            else
                return 0;
        }
        int flag=0;
        visit[s]=true;
        st.add(s);
        for(int u : adj[s]){
            if(u==p)continue;
            int ret = find_cycle(u,s);

            if(ret!=0){
                int top = st.peek();
                cycle[top]=true;
                st.pop();
                if(ret!=s)
                    flag=ret;
                else
                    flag=0;
            }
            else {
                if(!st.isEmpty())
                    st.pop();
            }
        }
        return flag;
    }
    static class FastReader{
        BufferedReader br;
        StringTokenizer st;

        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }
        String next(){
            while(st==null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch(IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt(){
            return Integer.parseInt(next());
        }
        double nextDouble(){
            return Double.parseDouble(next());
        }
        long nextLong(){
            return Long.parseLong(next());
        }
        String nextLind(){
            String str="";
            try{
                str=br.readLine();
            }catch (IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }
}

djm03178 님의 코드입니다.

이런 방식으로 싸이클을 찾을 것을 추천 합니다.

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[3005];
int st;
bool v[3005], cycle[3005];

void f(int i, int p)
{
	v[i] = true;
	for (int x : adj[i])
	{
		if (x != p)
		{
			if (v[x])
			{
				st = x;
				cycle[i] = true;
				return;
			}
			f(x, i);
			if (st)
				break;
		}
	}
	if (st)
		cycle[i] = true;
	if (st == i)
		st = 0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, i;
	cin >> n;
	for (i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	f(1, 0);
	for (i = 1; i <= n; i++)
	{
		if (cycle[i])
		{
			cout << "0 ";
			continue;
		}
		memset(v, 0, sizeof v);
		queue<int> q;
		q.push(i);
		v[i] = true;
		int t = 0;
		while (q.size())
		{
			for (int qq = q.size(); qq; qq--)
			{
				int cur = q.front();
				q.pop();
				if (cycle[cur])
				{
					cout << t << ' ';
					goto out;
				}
				for (int x : adj[cur])
				{
					if (!v[x])
					{
						v[x] = true;
						q.push(x);
					}
				}
			}
			t++;
		}
	out:;
	}
}