Subway Line#2

문제 복기

틀린 이유(틀린 부분)

1. 다음 좌표를 이전 좌표와 비교해서 같으면 진행하지 않아야하는데 비교하는 부분 빼먹음.

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

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)와 같다면 순환선이 돌아왔다는 것이고, 이후의 정점들은 순환선이 아니므로 음수값을 리턴한다!