DFS 스페셜 저지

문제

언어

  • JavaScript

순서도

  1. 인접리스트 형식의 그래프 생성
  2. 주어진 DFS 방문 순서에 대해서 index 를 기록
  3. 기록한 index 값을 기준으로 인접리스트 정렬
  4. DFS 탐색
  5. 올바른 순서인지 판별

문제 풀이 step 1

  • 백준 16940번 - BFS 스페셜 저지 풀이 와 유사하게 풀 수 있습니다. 탐색 방법만 달라집니다.
  • 주어진 입력을 통해서 나오는 DFS 탐색 순서가 올바른지 판별하는 함수를 만들어야 합니다.
  • 우선 주어지는 입력을 통해서 인접리스트 형식의 그래프를 생성합니다.
  • 그리고 주어지는 DFS 방문 순서를 기준으로 인접리스트를 정렬합니다.
    • 이렇게 정렬을 하기 위해서는 주어진 DFS 방문 순서에 대해서 index 를 기록해놔야 합니다.
    • 기록한 index 를 기준으로 인접리스트를 정렬합니다.
  • 그리고 DFS 탐색 시 탐색 순서를 기록해서 입력으로 주어진 DFS 방문 순서와 같은지 비교 하면 정답을 구할 수 있습니다.

소스 코드 1

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

const DFS = (graph, visited, from, dfsOrder) => {
	visited[from] = true;
	dfsOrder.push(from);

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

		DFS(graph, visited, to, dfsOrder);
	}
};

// 입력으로 주어진 방문 순서와 실제 DFS 탐색 순서를 비교하는 함수
const checkSame = (ans, dfsOrder) => {
	for (let i = 0; i < ans.length; i++) {
		if (ans[i] === dfsOrder[i]) continue;

		return 0;
	}

	return 1;
};

const solution = (input) => {
	const n = parseInt(input[0]);

	// 1. 인접리스트 형식의 그래프 생성
	const graph = Array.from({length: n + 1}, () => []);
	for (let i = 1; i < n; i++) {
		const [from, to] = input[i].split(" ").map(Number);

		graph[from].push(to);
		graph[to].push(from);
	}
	const ans = input[n].split(" ").map(Number);

	// 2. 주어진 방문 순서를 index 처리
	const order = [];
	for (let i = 0; i < ans.length; i++) {
		order[ans[i]] = i;
	}

	// 3. 주어진 방문 순서에 따라서 인접 리스트 정렬
	for (let i = 1; i < n + 1; i++) {
		graph[i].sort((a, b) => order[a] - order[b]);
	}

	// 4. DFS 탐색
	const dfsOrder = [];
	const visited = Array.from({length: n + 1}, () => false);
	DFS(graph, visited, 1, dfsOrder);

	// 5. 주어진 방문 순서와 실제 DFS 탐색 순서를 비교
	return checkSame(ans, dfsOrder);
};

console.log(solution(input));