# Subway Line#2

**틀린 이유(틀린 부분)**

1. 다음 좌표를 이전 좌표와 비교해서 같으면 진행하지 않아야하는데 비교하는 부분 빼먹음.
2. 이전 재귀함수에서 받은 res 값에 따라 리턴하는 값이 다르다!\
   아래 코드에서처럼 방문한 점 x 을 다시 방문하면 그 점을 리턴한다. 그럼 그 리턴값을 받은 함수 내에서도 값을 리턴해야하는데 이 때 리턴하는 값은 x를 리턴해야하는데 이 부분을 빼먹음.\
   x방문한 적이 있다 : 그 점 x가 시작점이고, 이후의 점들은 순환선이 아니다.\
   \=> 순환선이 아닌 점들에서 함수 리턴값도 처리해주었는데 정작 순환선에 속하는 점들에서 함수 리턴값을 빼먹어버림..!

```java
public static int dfs(int x,int p) {
		if(c[x]==1) return x;
		c[x] = 1;
		for(int y:a[x]) {
			if(y==p) continue;
			int res = dfs(y,x);
			//리턴된 res 값에 따라 리턴하는 값이 다르다! 
			if(res == -2) return -2;
			if(res>0) {
				c[x] = 2;
				if(res == x) return -2;
				else return res;
			}
		}
		return -1;
	}
```

일단 그냥 문제가 너무 어렵게 느껴졌다. 그럼에도 불구하고 아는 영역을 찾자면, 앞에서 풀어본 Two Dots 문제에서 싸이클을 찾는 부분이 공통 요소로 존재했다. 그래서 **이전의 위치와 현재의 위치, 다음 위치를 이용하여 탐색**을 하고, **다음위치로 방문한 점이 방문한 적이 있다면 싸이클이 존재**하는 것이고, **방문한 적이 있는 점은 그 싸이클의 시작점이 된다!!!!!!**

각 정점에서 순환선까지 거리 구하는 알고리즘 풀이 과정

1. 순환선을 찾는다.\
   순환선의 시작점을 찾는다.\
   순환선에 속하는 정점들을 찾는다.(찾아서 기록(저장))
2. n 개의 정점에서 순환선까지의 거리를 계산한다. - bfs 이용\
   거리를 저장하기 위한 dist 배열 생성\
   순환선에 속하는 정점들은 거리 0, \
   dist\[x] : 기준점(순환선에 속하는 정점들 또는 그 외의 좌표)에서 x까지의 거리

현재 위치와 이전 위치를 새로운 위치(다음 위치)와 현재 위치로 계속 갱신하면서 dfs 진행한다! 새로 방문한 x 위치에서 x가 이미 방문한 노드라면(check\[x] == 1) 그 x가 순환선의 시작점이므로 이 x를 리턴한다!

x를 계속 리턴하다가 먼저 호출된 재귀 함수내에서 현재위치 x가 리턴값(x)와 같다면 순환선이 돌아왔다는 것이고, 이후의 정점들은 순환선이 아니므로 음수값을 리턴한다!