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

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

728x90

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

해설 : 문제자체는 굉장히 간단합니다. 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 []adj; static Stack 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

djm03178 님의 코드입니다.

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

#include using namespace std; vector 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 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:; } }

728x90

from http://boomrabbit.tistory.com/193 by ccl(A) rewrite - 2021-11-20 19:01:29