그래프 행렬과 방문한 노드 체크용 행렬 생성시 n의 개수

Question

안녕하세요 선생님 좋은 강의 항상 잘 보고 있습니다 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을 초과하는 정점을 거쳐서 가는 경로도 있는 것 같아서요

콩팥팥죽 · Answer

그래프로도 만들어보다 잘못된 점을 알게됨 ㅋㅋㅋㅋ (이것도 양방향 노드까지 거쳐 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)) ;

콩팥팥죽 · Answer

앗 준영님 방가워요 저 제영이에요 그렇잖아도 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)) ;