문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

A는 B와 친구다.
B는 C와 친구다.
C는 D와 친구다.
D는 E와 친구다.
위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

코드(인접행렬) - 시간초과

var fs = require('fs');
const [n, ...line] = fs
	.readFileSync('/dev/stdin')
	.toString()
	.trim()
	.split('\n');
const [N, M] = n.split(' ').map((i) => Number(i));
const table = Array.from(Array(N), () => new Array(N).fill(0));

function solution() {
	let answer = 0;

	for (let i = 0; i < M; i++) {
		const [a, b] = line[i].split(' ');
		table[a][b] = 1;
		table[b][a] = 1;
	}

	function DFS(j, dfs) {
		if (dfs.length === 5) {
			answer = 1;
			return;
		}

		for (let i = 0; i < N; i++) {
			if (table[j][i] === 0 || dfs.includes(i)) continue;
			DFS(i, [...dfs, i]);
		}
	}

	for (let i = 0; i < N; i++) {
		DFS(i, [i]);
		if (answer === 1) break;
	}

	console.log(answer);
}

solution();

시간초과가 계속 나게 되서 다른 사람들의 풀이를 찾아보니 인접 행렬이 아닌 인접 리스트로 문제를 풀어야 시간 초과가 나지 않는다고 한다. 그래서 인접 리스트로 풀었는데...^^

코드(인접 리스트) - 시간초과

var fs = require('fs');
const [n, ...line] = fs
	.readFileSync('/dev/stdin')
	.toString()
	.trim()
	.split('\n');
const [N, M] = n.split(' ').map((i) => Number(i));
const table = Array.from(Array(N), () => []);
const visit = Array(N).fill(false);
let answer = 0;

function solution() {
	for (let i = 0; i < M; i++) {
		const [a, b] = line[i].split(' ');
		table[a].push(Number(b));
		table[b].push(Number(a));
	}

	function DFS(j, count) {
		if (answer) return;

		visit[j] = true;
		if (count === 5) {
			answer = 1;
			return;
		}

		for (let i = 0; i < table[j].length; i++) {
			const number = table[j][i];
			if (!visit[number]) {
				DFS(number, count + 1);
			}
		}
		visit[j] = false;
	}

	for (let i = 0; i < N; i++) {
		if (answer) break;
		DFS(i, 1);
	}

	console.log(answer);
}

solution();

다른 사람 풀이랑 비교했을때 코드 사용 방식이 조금씩 다르긴 했지만 푸는 방식은 같은데 왜 내것만 시간 초과가 뜨는지....

원인은 입력할때 받는 방식에서 시간이 오래걸렸던 거였다...

//시간초과 나왔던 방식
var fs = require('fs');
const [n, ...line] = fs
	.readFileSync('/dev/stdin')
	.toString()
	.trim()
	.split('\n');
const [N, M] = n.split(' ').map((i) => Number(i));

for (let i = 0; i < M; i++) {
		const [a, b] = line[i].split(' ');
		table[a].push(Number(b));
		table[b].push(Number(a));
	}

//시간초과가 안나온 방식
var fs = require('fs');
const input = fs
	.readFileSync('/dev/stdin')
	.toString()
	.trim()
	.split('\n')
	.map((v) => v.split(' ').map(Number));
const [N, M] = input.shift();

for (let i = 0; i < M; i++) {
		const [a, b] = input[i];
		table[a].push(b);
		table[b].push(a);
	}

사실 둘을 비교했을때 split을 먼저 해주냐 나중에 해주냐 차이로 밖에 안보이는데 왜 이렇게 시간차이가 많이 난건지...?(왜 이런지 아시는 분은 알려주세요...)

최종 코드 🎉

var fs = require('fs');
const input = fs
	.readFileSync('/dev/stdin')
	.toString()
	.trim()
	.split('\n')
	.map((v) => v.split(' ').map(Number));
const [N, M] = input.shift();
const table = Array.from(Array(N), () => []);
const visit = Array(N).fill(false);
let answer = 0;

function solution() {
	for (let i = 0; i < M; i++) {
		const [a, b] = input[i];
		table[a].push(b);
		table[b].push(a);
	}

	function DFS(j, count) {
		if (answer) return;

		visit[j] = true;
		if (count === 5) {
			answer = 1;
			return;
		}

		for (let i = 0; i < table[j].length; i++) {
			const number = table[j][i];
			if (!visit[number]) {
				DFS(number, count + 1);
			}
		}
		visit[j] = false;
	}

	for (let i = 0; i < N; i++) {
		if (answer) break;
		DFS(i, 1);
	}

	console.log(answer);
}

solution();