인프런 커뮤니티 질문&답변
작성한 질문수
그래프 행렬과 방문한 노드 체크용 행렬 생성시 n의 개수
작성
·
205
0
안녕하세요 선생님
좋은 강의 항상 잘 보고 있습니다
let ch=Array.from({length:n+1}, ()=>0)
let graph=Array.from(Array(n+1), ()=>Array(n+1).fill(0))
그래프 행렬과 방문한 노드 체크용 행렬 생성시
n+1개 만큼 생성되도록 설정해 주셨는데
이 부분은 입력예제에 맞춤형 설정일까요??
왜냐하면 만약 문제가 1번 정점 -> 3번 정점
으로 가는 경로를 찾는다면 n이 3이되지만
실제로는 1 -> 4 -> 2 -> 3 처럼 n을 초과하는
정점을 거쳐서 가는 경로도 있는 것 같아서요
답변 2
0
그래프로도 만들어보다 잘못된 점을 알게됨 ㅋㅋㅋㅋ
(이것도 양방향 노드까지 거쳐 5번가는 경우의수 - 즉 중복됨)
function solution(n,arr) {
let answer=0;
let graph=Array.from(Array(n+1),() => Array(n+1).fill(0));
let ch=Array.from(Array(n+1),() => Array(n+1).fill(0));
let path=[];
let result = [];
for(let [a,b] of arr) {
graph[a][b]=1;
}
function DFS(v) {
if(v===n) {
answer++;
result.push(Array.from(path));
}
else {
for(let i=1; i<=arr.length; i++) {
if(graph[v][i]===1 && ch[v][i] === 0) {
ch[v][i] = 1;
path.push(i);
DFS(i);
ch[v][i] = 0;
path.pop();
}
}
}
}
path.push(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));
0
앗 준영님 방가워요 저 제영이에요
그렇잖아도 19가지가 나오는데 뭐지..? 이러고 잇엇는데
제가 짠건데 이럼 19가지 나옴 아직 머가 틀린건지 몰라서
이제 강의볼라구요 방가워서 댓글남겻어요
*말씀대로 7번 거쳐가는 경우도 잇어요
ex)[1, 4][4, 2][2, 1][1, 2][2, 3][3, 4][4, 5]
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
*아 이렇게하면 4번을 두번 거쳐가네요 안되는듯
문제상 양방향 노드를 거쳐서 5번을 가려면 반드시
노드를 중복해서 가게 되있네요
제가 짠건 양뱡향 노드를 거쳐서 5번을 가는 경우의수도 포함
따라서 샘 코드가 정확합니다
function solution(n, arr){
let answer=[];
let temp= [];
let checkIdx = Array.from({ length: arr.length },()=>0);
function DFS(L,v) {
if(v===n) {
answer.push(Array.from(temp));
}else {
for(let i=0; i<arr.length; ++i) {
if(arr[i][0] === v) {
if(checkIdx[i] === 0) {
checkIdx[i] = 1;
temp[L] = arr[i];
DFS(L+1,temp[L][1]);
checkIdx[i] = 0;
temp.pop();
}
}
}
}
}
DFS(0,1)
return answer;
}
//* 1번 방문한 노드는 2번 방문해서는 안된다
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));