IF - 경로탐색

문제 및 예시

지난 풀이 참고

풀이 및 회고

• 지난 풀이에서는 이미 방문한 노드를 DFS의 깊이와 for문의 i를 가지고만 검사를 했었던게 실패 이유였다.
• 이번에는 이전 DFS 문제들에서 해왔던 것처럼 체크배열을 만들어서, DFS로 깊이가 더해지는 중에는 이미 방문한 노드를 방문하지 않도록 처리했다.
• 인접행렬을 이용한 풀이는 다른 노드로 향하는 간선이 없는 경우엔 2차원 배열을 0으로 채운다.
• 인접행렬은 노드 개수 엄청 많을 때는 시간복잡도가 너무 높고, 메모리도 많이 차지한다는 문제가 있다. 그래서 인접리스트로도 풀었다.
• 인접리스트는 인접행렬과 달리 2차원배열을 0으로 채우지 않고, 간선이 가리키는 노드의 번호로 채운다. 1번 노드와 연결된 2,3,4,5가 2차원배열의 원소가 되는 셈이다.

코드 (인접행렬)

const solution = (nodeCnt, linkInfo) => {
	let answer = 0;
	const matrix = Array.from(Array(nodeCnt + 1), () => Array(nodeCnt + 1).fill(0));
	for (let [a, b] of linkInfo) matrix[a][b] = 1;
	const path = [];
	const check = Array(nodeCnt + 1).fill(0);

	const DFS = (v) => {
		if (v === nodeCnt) {
			answer++;
			console.log(path);
		} else {
			for (let i = 1; i <= nodeCnt; i++) {
				if (check[i] === 0 && matrix[v][i] === 1) {
					check[i] = 1;
					path.push(i);
					DFS(i);
					path.pop();
					check[i] = 0;
				}
			}
		}
	};

	check[1] = 1;
	path.push(1);
	DFS(1);
	console.log(answer);
	return answer;
};

코드(인접리스트)

const solution = (nodeCnt, linkInfo) => {
	let answer = 0;
	const list = Array.from(Array(nodeCnt + 1), () => []);
	const check = Array(nodeCnt + 1).fill(0);
	for (let [a, b] of linkInfo) list[a].push(b);
	const path = [];

	const DFS = (v) => {
		if (v === nodeCnt) {
			answer++;
			console.log(path);
		} else {
			for (let i = 0; i < list[v].length; i++) {
				if (check[list[v][i]] === 0) {
					check[list[v][i]] = 1;
					path.push(list[v][i]);
					DFS(list[v][i]);
					check[list[v][i]] = 0;
					path.pop();
				}
			}
		}
	};
	check[1] = 1;
	path.push(1);
	DFS(1);
	console.log(answer);
	return answer;
};