문제
방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는
12345
125
13425
1345
1425
145
총 6 가지입니다.
[입력설명]
첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연 결정보가 주어진다.
[출력설명]
총 가지수를 출력한다.
입력예제 1
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5
출력예제 1
6
문제 풀이
예습이론
- 인접행렬은, 노드의 개수가 적을 때 사용할 수 있는 방법이다. 만약 노드의 개수가 많다면 인접행렬이아닌 인접그래프 방식을 이용한다.(다음문제 참고)
Array.from(Array(n+1), ()=>Array(n+1).fill(0))는 행이 n+1개, 열이 n+1개인 유사배열을 만든다. 아래 코드에서 행과 열의 개수를 n+1으로 설정한 이유는, 인덱스 1번부터 사용하기 위해서이다.(0번 비워둠)
코드
- DFS로 풀이할 수 있는 문제이다. 인접행렬 graph를 만들어주고, 방문한 노드인지 체크하기 위해 ch배열을 만든다.
graph[v][i]===1의 의미는 v에서 i로 이동할 수 있다는 뜻이다. 무조건 1번에서 시작하기 때문에 초기코드가DFS(1)이다. 이로인해 DFS(1)에서graph[1][i]가 되는데, 이는 1에서 i로 이동할 수 있는지 체크한다.
같은 원리로path.push(i)를 하면,DFS(i)를 해준다. i부터 출발한다는 의미이다.- 코드 전체 풀이 원리는 다음과 같다.
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
//n: 정점 갯수, arr:간선 정보
function solution(n, arr){
let answer=0;
let graph=Array.from(Array(n+1), ()=>Array(n+1).fill(0)); //graph: 인접행렬을 만들 2차원 배열
let ch=Array.from({length:n+1}, ()=>0);
path=[]; //테스트 코드 path(경로)
//인접 행렬
for(let [a, b] of arr){
//console.log(a, b);
graph[a][b]=1; //방향그래프
}
function DFS(v){
if(v===n){
answer++;
console.log(path);
}
else{
//가지뻗기
for(let i=1; i<=n; i++){
//v->i로 이동할 수 있고 ~
if(graph[v][i]===1 && ch[i]===0){
ch[i]=1;
path.push(i);
DFS(i); //2를 넣었으면, D(2)가 됨(출발을 2부터 함)
ch[i]=0;
path.pop(); //back 할 때
}
}
}
}
path.push(1); //출발점 1은 무조건 처음에 push
ch[1]=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
체크 반드시 해줘야함