BFS 스페셜 저지

문제

언어

  • JavaScript

순서도

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

문제 풀이 step 1

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

소스 코드 1

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

// 간단한 Queue 구현
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;
	}
}

const BFS = (graph, visited) => {
	const queue = new Queue();
	const bfsOrder = [1];
	visited[1] = true;
	queue.enqueue(1);

	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;
			bfsOrder.push(to);
			queue.enqueue(to);
		}
	}

	return bfsOrder;
};

const checkSame = (ans, bfsOrder) => {
	for (let i = 0; i < ans.length; i++) {
		if (ans[i] === bfsOrder[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. 주어진 BFS 방문 순서에 대해서 index 를 기록
	const order = [];
	for (let i = 0; i < ans.length; i++) {
		order[ans[i]] = i + 1;
	}

	// 3. 기록한 index 값을 기준으로 인접리스트 정렬
	for (let i = 1; i < n + 1; i++) {
		graph[i].sort((a, b) => order[a] - order[b]);
	}

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

	// 5. 올바른 순서인지 판별
	return checkSame(ans, bfsOrder);
};

console.log(solution(input));