너비우선탐색
-
문제 73. 최단 경로 찾기🧠 codingtest/javascript 100제 2022. 4. 12. 07:04
입력받은 두정점이 공백으로 구분되어 주어질때, 두 정점 사이를 이동할 수 있는 최단 거리를 출력하는 프로그램을 작성하여라. 이때 최단 거리란, 정점의 중복없이 한 정점에서 다른 정점까지 갈 수 있는 가장 적은 간선의 수를 의미 // 데이터 graph = { A: ["B", "C"], B: ["A", "D", "E"], C: ["A", "F"], D: ["B"], E: ["B", "F"], F: ["C", "E"], } // 입력 A F // 출력 2 미리 생각해 봐야할 것 너비우선 탐색을 이용한다 그림을 그려보며 어떠한 방식으로 추척(?)할 것인가 생각한다. 답 let graph = { A: ["B", "C"], B: ["A", "D", "E"], C: ["A", "F"], D: ["B"], E: ["B..
-
문제 72. 너비 우선 탐색🧠 codingtest/javascript 100제 2022. 4. 9. 08:56
"너비우선탐색" 이란? 어떤 노드를 방문하여 확인한 후, 목표한 노드가 아니면 그 노드와 연결된 정점들 중에서 우선순위가 동일한 다른 노드를 찾고 그 순위에 없으면 그 다음 순위노드를 차례대로 찾는 방법이다.(깊이우선탐색의 연장선) // 데이터 graph = { E: ["D", "A"], F: ["D"], A: ["E", "C", "B"], B: ["A"], C: ["A"], D: ["E", "F"], }; // 출력 E D A F C B 미리 생각해 봐야할 것 순서, 객체접근방식(키값, 벨류값 추출방식) 답 let graph = { E: ["D", "A"], F: ["D"], A: ["E", "C", "B"], B: ["A"], C: ["A"], D: ["E", "F"], }; function dfs..