촌수계산

문제

언어

  • JavaScript

순서도

  1. 여러 사람들에 대한 부모 자식 관계를 인접리스트 형식의 그래프로 변환
  2. 두 사람 중 한 사람을 시작점으로 해서 DFS 탐색 진행
    1. 이 때, 각 사람을 탐색 하며 촌수를 계산
  3. 두 사람의 촌수를 출력

문제 풀이 step 1

  • 여러 사람들에 대한 부모 자식들 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 문제입니다.
  • 촌수란
    • 부모와 자식 사이는 1 촌입니다.
    • 저와 아버지, 아버지와 할아버지는 1 촌으로 저와 할아버지는 2 촌입니다.
    • 아버지 형제들과 할아버지는 1 촌, 나와 아버지 형제들과는 3 촌입니다.
  • 본 문제는 주어진 두 사람 중 한 사람을 시작점으로 해서 DFS 탐색을 통해서 각 사람들과의 촌수를 구하면 쉽게 풀 수 있는 문제입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드

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

const dfs = (relation, distance, destination, from) => {
	if (distance[destination] !== -1) return;

	// 이미 계산한 사람을 제외하고, 촌수를 게산하며 DFS 탐색 진행
	for (let i = 0; i < relation[from].length; i++) {
		const to = relation[from][i];

		if (distance[to] !== -1) continue;

		distance[to] = distance[from] + 1;
		dfs(relation, distance, destination, to);
	}
};

const solution = (input) => {
	const n = Number(input[0]);
	const [x, y] = input[1].split(" ").map(Number);

	// 여러 사람들에 대한 부모 자식들 간의 관계로 인접 리스트 생성
	const relation = Array.from({length: n + 1}, () => []);
	const m = Number(input[2]);
	for (let i = 3; i < 3 + m; i++) {
		const [from, to] = input[i].split(" ").map(Number);

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

	// 시작점을 제외한 모든 사람들의 촌수를 -1 로 초기화 후 DFS 탐색 진행
	const distance = Array(n + 1).fill(-1);
	distance[x] = 0;
	dfs(relation, distance, y, x);

	return distance[y];
};

console.log(solution(input));