ABCDE

문제

언어

  • JavaScript

문제 풀이 step 1

  • 문제에서 원하는 것은
    • 주어진 친구들을 정점, 친구 관계를 간선으로 만들고,
    • 한 정점에서 탐색을 시작해서 갈 수 있는 정점까지 갔을 때 그 경로의 길이가 4 이상인 경로가 있는지 없는지 입니다.
  • 우선, 주어진 친구들과 친구 관계를 이용해서 인접리스트 형식으로 그래프를 만듭니다.
  • 그리고 한 정점씩 DFS 방식으로 모든 경로를 탐색합니다.
  • 단, 탐색 후 돌아오면서 다시 방문 처리를 취소해야 합니다.
    • 왜냐하면 단순히 끝까지 갈 수 있는 경로를 구하는 것이 아닌 갈 수 있는 모든 경로를 탐색해야 하기 때문입니다.

주의할 점

  • 문제가 원하는 친구 관계를 찾았으면 그 이후로는 탐색을 종료해야합니다.
  • 그 이후로도 탐색을 하게 하면 시간 초과가 발생합니다.
  • 즉, 백트래킹을 이용해서 더이상의 의미없는 탐색은 하지 않습니다.

소스 코드 1

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

let count = 0;

const dfs = (graph, from, visited, depth) => {
	if (count < depth) count = depth;

	// 문제에서 원하는 친구 관계를 찾았다면 더이상의 탐색은 무의미함
	if (count >= 4) return;

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

		visited[to] = true;
		dfs(graph, to, visited, depth + 1);

		// 돌아오면서 방문 처리 취소, 갈 수 있는 모든 경로를 탐색해보기 위해서
		visited[to] = false;
	}
};

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

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

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

	// 각 정점마다 DFS 탐색 진행
	for (let i = 0; i < n; i++) {
		const visited = Array.from({length: n}, () => false);
		visited[i] = true;
		dfs(graph, i, visited, 0);

		if (count >= 4) return 1;
	}

	return 0;
};

console.log(solution(input));