IF - 인접행렬 경로탐색(실패)

문제

방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프
로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는

1 2 3 4 5
1 2 5
1 3 4 2 5
1 3 4 5
1 4 2 5
1 4 5
총 6가지 입니다.

예시

nodeCnt	linkInfo	Output
5	[[1, 2],[1, 3],[1, 4],[2, 1],[2, 3],[2, 5],[3, 4],[4, 2],[4, 5]]	6

풀이 및 회고

• 지금까지 배운 DFS를 활용해서 특정 노드까지의 경로들의 경우의 수를 구하는 문제이다.
• 그래프를 만든 것까지는 좋았으나, DFS로 깊이를 더하는 과정에서 이미 방문한 노드 조건 검사를 단순히 i > L 로 처리해 버린 게 실패 요인인 것 같다. (답만 맞았다.)
• 너무 쉽게 풀린다 해서 경로들을 직접 콘솔에 찍어보니 [ 2, 3, 4, 5 ] [ 5, 4, 5 ] [ 3, 3, 4, 5 ] [ 5, 4, 5 ] [ 4, 3, 4, 5 ] [ 5, 4, 5 ] 와 같은 잘못된 경로들을 보여주고 있었다.

코드

const solution = (nodeCnt, linkInfo) => {
	let answer = 0;
	const matrix = Array.from(Array(nodeCnt + 1), () => Array(nodeCnt + 1).fill(0));

	const DFS = (L, currNode) => {
		if (L === nodeCnt && currNode === nodeCnt) {
			answer++;
		} else {
			for (let i = 1; i <= matrix[L].length; i++) {
				if (matrix[L][i] && i > L) DFS(L + 1, i);
			}
		}
	};

	for (let i = 0; i < linkInfo.length; i++) {
		matrix[linkInfo[i][0]][linkInfo[i][1]] = 1;
	}
	DFS(1, 1);
	return answer;
};