인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

인프런 커뮤니티 질문&답변

김준영님의 프로필 이미지
김준영

작성한 질문수

자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)

2. 경로탐색(DFS-인접행렬 : 노드개수가 적을 때)

그래프 행렬과 방문한 노드 체크용 행렬 생성시 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));
김준영님의 프로필 이미지
김준영

작성한 질문수

질문하기