문제
앞의 문제(9-2)와 동일
문제 풀이
예습 이론
- 앞 문제에서 사용했던 인접행렬은, 시간복잡도가 높고 메모리도 많이 차지한다. 그러나 인접리스트는 시간복잡도가 낮으며 메모리도 많이 차지하지 않는다. 따라서 노드의 개수가 많아지면 인접리스트를 사용하는것이 좋다.
- 인접리스트의 원리는 다음과 같다. 앞에서 봤던 인접행렬과 비교해보자!
코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(n, arr){
let answer=0;
let graph=Array.from(Array(n+1), ()=>Array()); //인접리스트 만듦
let ch=Array.from({length:n+1}, ()=>0);
let path=[]; //테스트 코드 path(경로)
//인접리스트
for(let [a, b] of arr){
graph[a].push(b);
}
console.log(graph);
function DFS(v){
if(v===n){
answer++;
console.log(path);
}
else{
for(let i=0; i<graph[v].length; i++){
if(ch[graph[v][i]]===0){
ch[graph[v][i]]=1;
path.push(graph[v][i]);
DFS(graph[v][i]); //push한것에서부터 출발
ch[graph[v][i]]=0;
path.pop();
}
}
}
}
path.push(1); //출발점 1은 무조건 처음에 push
ch[1]=1;
DFS(1);
return answer;
}
let arr=[[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5]];
console.log(solution(5, arr));
</script>
</body>
</html>
내가 짱이다 😎 매일 조금씩 성장하기🌱
9/18
그림 그려보면서 차근차근 풀어보기