DFS와 BFS

문제

언어

  • JavaScript

문제 풀이 step 1

  • 주어진 입력을 통해서 인접 리스트 방식으로 그래프를 구현합니다.
  • 문제에서 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하라고 했습니다.
  • 따라서 인접 리스트의 각 리스트를 오름차순으로 정렬합니다.
  • DFS 탐색을 수행하며 방문한 정점을 순서대로 기록합니다.
  • BFS 탐색을 수행하며 방문한 정점을 순서대로 기록합니다.
  • 적절한 형태의 문자열로 변환하면 정답입니다.

소스 코드

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

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

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

		dfs(graph, visited, next, dfsOrder);
	}
};

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

	// 인접 리스트 구현
	for (let i = 1; i < m + 1; i++) {
		const [from, to] = input[i].split(" ").map(Number);

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

	// 정점 번호가 작은 것을 먼저 방문할 수 있도록 정렬
	graph = graph.map((v) => v.sort((a, b) => a - b));

	// dfs
	let visited = Array.from({length: n + 1}, () => false);
	const dfsOrder = [];
	dfs(graph, visited, v, dfsOrder);

	// bfs
	visited = visited.map((v) => false);
	const bfsOrder = [v];
	const queue = [v];
	visited[v] = true;
	while (queue.length) {
		const now = queue.shift();

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

			visited[next] = true;
			bfsOrder.push(next);
			queue.push(next);
		}
	}

	return dfsOrder.join(" ") + "\n" + bfsOrder.join(" ");
};

console.log(solution(input));