카테고리 없음
백준 16947 - 서울지하철 2호선 ( 트리 내 사이클 찾기 ) ( java)
jin_j_i_n
2021. 4. 1. 13:37
16947번: 서울 지하철 2호선
첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호
www.acmicpc.net
백준 강의를 들으면서 Two Dots 문제 풀었던 것 처럼 사이클을 찾으려고 했지만 어딘가 잘못된건지 자꾸 사이클 이외의 노드까지 포함되버렸다.
강의를 안듣고 최대한 찾아보려 했지만 하루 이상 걸려버려 그냥 들었는데 어떻게 이런 코드를 생각해내지....싶었다
암튼 문제를 푸는데에 핵심 과정은
1. 사이클을 찾는다
2. 사이클안의 노드에서 이외의 노드들까지의 최소거리를 bfs, 혹은 dfs로 찾으며 최소값을 갱신해준다.
이다.
1. 사이클을 찾는다
public static int go(int x , int p ){
// return 값
// -2 : 사이클을 찾았으나 현재 노드는 사이클에 속하지 않음
// -1 : 사이클을 찾지 못함
// 0~ n-1 : 사이클을 찾았고 , 해당값은 시작 인덱스임
// x : 현재 노드 , p : 이전 노드
if(check[x] == 1) return x;
check[x] = 1;
for(int y : arr[x]) {
if(y == p) continue; // 이전 노드를 재방문 한거면 생략
int res = go(y, x); //다음번 노드 검사
if(res == -2) return -2; //사이클을 찾았으나 사이클에 속하지 않음
if(res >=0 ) {
check[x] = 2;
if(x == res) return -2; //시작 정점을 찾았다면, 해당 노드로부터 이전의 노드는 사이클에 속하지 않는 노드들이므로 -2를 리턴한다.
else return res; //아니면 시작노드를 찾을때까지 -2 리턴
}
}
return -1; //사이클을 찾지 못함
}dfs를 돌리면서 각 노드들이 스텍에 쌓이는걸 생각해보면서 해당 코드를 살펴보자.
예제 2번을 생각해보면 시작정점이 6이라면, 6 4 3 2 1 순으로 방문했다 가정하고, 이 상태에서 또 3을 방문한다면, 스텍에 쌓여있는 3을 찾아 전부 사이클 안에 있는 노드임을 표시해주고 , 그 이전에 있는 노드들 ( 6, 4 ) 는 사이클을 찾은 상태에서 사이클 노드가 아님을 표시해주면 된다.
따라서 소스코드를 보면, 리턴값에 따라 상태가 다르다. -2를 리턴하면 사이클을 찾았고 현재 노드는 사이클에 속하지 않음을 나타낸다, 이경우는 그 이전에 있는 노드는 사이클에 속하지 않으므로 계속 -2를 리턴해주면 된다.
-1을 리턴한다면 사이클이 존재하지 않음을 리턴한다.
그 이외의 값을 리턴한다면 노드 값을 리턴한다는 뜻이고, 해당 값은 사이클이 시작하는 노드의 값이다. 사이클을 시작하는 노드를 찾았다면 (check[x] == 1) 스텍에 쌓여있는 노드들 중 시작노드를 찾을때 까지 해당 값을 리턴한다.
위와 같은 과정으로 사이클을 찾으면 된다.
소스코드
import java.io.*;
import java.util.*;
public class B16947 {
static int[] check;
static int N;
static int[] Dis;
static ArrayList[] arr;
static ArrayList Cycle;
static boolean getCycle = false;
public static int go(int x , int p ){
// return 값
// -2 : 사이클을 찾았으나 현재 노드는 사이클에 속하지 않음
// -1 : 사이클을 찾지 못함
// 0~ n-1 : 사이클을 찾았고 , 해당값은 시작 인덱스임
// x : 현재 노드 , p : 이전 노드
if(check[x] == 1) return x;
check[x] = 1;
for(int y : arr[x]) {
if(y == p) continue; // 이전 노드를 재방문 한거면 생략
int res = go(y, x); //다음번 노드 검사
if(res == -2) return -2; //사이클을 찾았으나 사이클에 속하지 않음
if(res >=0 ) {
check[x] = 2;
if(x == res) return -2; //시작 정점을 찾았다면, 해당 노드로부터 이전의 노드는 사이클에 속하지 않는 노드들이므로 -2를 리턴한다.
else return res; //아니면 시작노드를 찾을때까지 -2 리턴
}
}
return -1; //사이클을 찾지 못함
}
public static void bfs(int start) {
boolean[] visit = new boolean[N+1];
int[] cnt = new int[N+1];
Queue que = new LinkedList<>();
que.add(start);
visit[start] = true;
while(!que.isEmpty()) {
int x = que.poll();
for(int i=0 ; i<arr[x].size() ; i++) {
int nx = arr[x].get(i);
if(!visit[nx]) {
visit[nx] = true;
cnt[nx] = cnt[x] + 1;
que.add(nx);
}
}
}
// System.out.println("start : "+ start);
for(int i=1 ; i<=N; i++) {
Dis[i] = Math.min(Dis[i], cnt[i]);
}
// System.out.println();
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new ArrayList[N+1];
Dis = new int[N+1];
for(int i=1; i<=N; i++) {
Dis[i] = Integer.MAX_VALUE;
arr[i] = new ArrayList();
}
String[] inputs;
for(int i=0 ; i<N; i++) {
inputs = br.readLine().split(" ");
int a = Integer.parseInt(inputs[0]);
int b = Integer.parseInt(inputs[1]);
arr[a].add(b);
arr[b].add(a);
}
check = new int[N+1];
for(int i=1 ; i<=N; i++) {
int res = go(1, 0);
if(res != -1) break;
}
for(int i=1 ; i<=N; i++) {
if(check[i] == 2)
bfs(i);
}
for(int i=1 ; i<=N; i++) {
System.out.print(Dis[i] +" ");
}
System.out.println();
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | import java.io.*; import java.util.*; public class B16947 { static int[] check; static int N; static int[] Dis; static ArrayList<Integer>[] arr; static ArrayList<Integer> Cycle; static boolean getCycle = false; public static int go(int x , int p ){ // return 값 // -2 : 사이클을 찾았으나 현재 노드는 사이클에 속하지 않음 // -1 : 사이클을 찾지 못함 // 0~ n-1 : 사이클을 찾았고 , 해당값은 시작 인덱스임 // x : 현재 노드 , p : 이전 노드 if(check[x] == 1) return x; check[x] = 1; for(int y : arr[x]) { if(y == p) continue; // 이전 노드를 재방문 한거면 생략 int res = go(y, x); //다음번 노드 검사 if(res == -2) return -2; //사이클을 찾았으나 사이클에 속하지 않음 if(res >=0 ) { check[x] = 2; if(x == res) return -2; //시작 정점을 찾았다면, 해당 노드로부터 이전의 노드는 사이클에 속하지 않는 노드들이므로 -2를 리턴한다. else return res; //아니면 시작노드를 찾을때까지 -2 리턴 } } return -1; //사이클을 찾지 못함 } public static void bfs(int start) { boolean[] visit = new boolean[N+1]; int[] cnt = new int[N+1]; Queue<Integer> que = new LinkedList<>(); que.add(start); visit[start] = true; while(!que.isEmpty()) { int x = que.poll(); for(int i=0 ; i<arr[x].size() ; i++) { int nx = arr[x].get(i); if(!visit[nx]) { visit[nx] = true; cnt[nx] = cnt[x] + 1; que.add(nx); } } } // System.out.println("start : "+ start); for(int i=1 ; i<=N; i++) { Dis[i] = Math.min(Dis[i], cnt[i]); } // System.out.println(); } public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); arr = new ArrayList[N+1]; Dis = new int[N+1]; for(int i=1; i<=N; i++) { Dis[i] = Integer.MAX_VALUE; arr[i] = new ArrayList<Integer>(); } String[] inputs; for(int i=0 ; i<N; i++) { inputs = br.readLine().split(" "); int a = Integer.parseInt(inputs[0]); int b = Integer.parseInt(inputs[1]); arr[a].add(b); arr[b].add(a); } check = new int[N+1]; for(int i=1 ; i<=N; i++) { int res = go(1, 0); if(res != -1) break; } for(int i=1 ; i<=N; i++) { if(check[i] == 2) bfs(i); } for(int i=1 ; i<=N; i++) { System.out.print(Dis[i] +" "); } System.out.println(); } } | cs |