서울 지하철 2호선

문제

언어

  • JavaScript

순서도

  1. 입력을 토대로 인접리스트 형식의 그래프 생성
  2. 1 번 노드부터 시작해서 DFS 탐색으로 사이클인 정점들 찾기
  3. BFS 탐색으로 사이클인 정점들로부터 사이클에 포함되지 않는 정점들의 거리를 구한다.

순서도 세부 1

  • DFS 탐색
    • 사이클의 시작점 찾기
      • 출발 노드에서 갈 수 있는 노드 중에서 방문한 노드를 기준으로 검사 진행
      • 만약 출발 노드에서 방문한 노드와의 거리가 2 이상이라면, 그 방문한 노드는 사이클의 시작점이다.
      • 사이클의 시작점을 찾은 이후의 탐색은 무의미하므로 이후로의 탐색은 return 처리
    • 사이클에 포함되는 정점들에 대해서 마킹
      • 재귀 호출이 반환되는 부분에서 맨 처음 호출했을 때까지 올라감
      • 올라가면서 사이클의 시작점 전까지 모두 사이클에 포함됨을 마킹

순서도 세부 2

  • BFS 탐색
    • 사이클에 포함되는 정점들은 방문 처리만 진행
    • 사이클에 포함되지 않는 정점들은 방문 처리에 추가로 거리를 기록

문제 풀이 step 1

  • 사이클을 찾고, 사이클에 포함되지 않는 정점들은 사이클로부터의 거리를 구해야 합니다.
  • DFS 탐색을 통해서 사이클을 찾아야 합니다.
    • 이는 예전에 풀었던 Two Dots 문제에서 영감을 얻을 수 있습니다.
    • 영감은 바로 사이클의 시작점이 되기 위한 조건입니다.
    • 그 조건은 서로 다른 점이어야 하며, 거리 차이가 2 이상 나야 한다는 것입니다. (거리차이는 그래프의 모양에 영향 받음)
    • 이렇게 사이클의 시작점을 찾았으면, 사이클에 포함되는 정점들을 찾아야 합니다. (상당히 어려운 부분)
      • DFS 탐색 재귀 호출을 반환하면서 사이클에 포함되는 정점들에 대해서 사이클에 포함된다는 것을 마킹하면 됩니다.
      • 반환 했을 때 사이클인 노드로부터 반환되었을 때의 노드만 사이클에 포함된다고 마킹합니다.
      • 그리고 사이클의 시작점이면 이후의 반환에 대해서는 마킹을 하지 않습니다.

후기

  • 꼭 다시 풀어볼 문제입니다.
  • 이 문제를 해결하기 위해서 거의 3 ~ 4 시간은 사용한 것 같습니다.
  • DFS 탐색에 대해서 더 깊게 배울 수 있었고, 추가로 재귀 호출에 대해서 더욱 깊게 배울 수 있었습니다.

소스 코드 1

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

class Queue {
	constructor() {
		this.bucket = [];
		this.front = -1;
		this.rear = -1;
	}

	enqueue(data) {
		this.bucket[++this.front] = data;
	}

	dequeue() {
		if (!this.isEmpty()) return this.bucket[++this.rear];
	}

	isEmpty() {
		return this.front === this.rear;
	}
}

let find = 0;

const DFS = (n, graph, dist, cycle, from, depth) => {
	// 사이클의 시작점을 찾으면 이후의 탐색은 무의미
	if (find) return;

	// 현재의 노드에서 갈 수 있는 노드들 중에서 방문한 노드들 기준으로 비교 진행
	// 사이클이라면 거리 차이가 2 이상 남
	for (let i = 0; i < graph[from].length; i++) {
		const to = graph[from][i];
		if (dist[to] === 0) continue;

		// 사이클의 시작점을 찾았으면 시작점을 기록하고 현재의 점이 사이클이 포함됨을 표시
		if (Math.abs(dist[from] - dist[to]) >= 2) {
			find = to;
			cycle[from] = true;
			return;
		}
	}

	// 현재의 노드에서 갈 수 있는 노드 들 중에서 방문하지 않은 노드들 기준으로 탐색 진행
	for (let i = 0; i < graph[from].length; i++) {
		const to = graph[from][i];
		if (dist[to] !== 0) continue;

		dist[to] = depth + 1;
		DFS(n, graph, dist, cycle, to, depth + 1);

		// 재귀 호출이 반환되면서 사이클의 시작점 전까지의 노드들을 사이클에 포함시킴
		if (cycle[find]) return;
		// 반환 시 사이클인 노드로부터 반환 되었을 때만 사이클에 포함시킴
		if (cycle[to]) cycle[from] = true;
	}
};

const BFS = (graph, cycle, visited, dist, find) => {
	const queue = new Queue();
	visited[find] = true;
	queue.enqueue(find);

	// 사이클에 포함되지 않는 노드들만 거리 값을 계산
	while (!queue.isEmpty()) {
		const from = queue.dequeue();

		for (let i = 0; i < graph[from].length; i++) {
			const to = graph[from][i];
			if (visited[to]) continue;

			visited[to] = true;
			if (!cycle[to]) dist[to] = dist[from] + 1;
			queue.enqueue(to);
		}
	}
};

const solution = (input) => {
	const n = parseInt(input[0]);
	const graph = Array.from({length: n + 1}, () => []);
	for (let i = 1; i < n + 1; i++) {
		const [from, to] = input[i].split(" ").map(Number);

		graph[from].push(to);
		graph[to].push(from);
	}

	const cycle = Array.from({length: n + 1}, () => false);
	let dist = Array.from({length: n + 1}, () => 0);
	// DFS 탐색을 하며 사이클인 정점들 찾기
	dist[1] = 1;
	DFS(n, graph, dist, cycle, 1, 1);

	dist = Array.from({length: n + 1}, () => 0);
	const visited = Array.from({length: n + 1}, () => false);
	// BFS 탐색을 하며 역과 순환선 사이의 거리 구하기
	BFS(graph, cycle, visited, dist, find);

	// 의미상 편리하게 하기 위한 0 번 index 값 제거
	dist.shift();

	return dist.join(" ");
};

console.log(solution(input));