문제 정보 프로그래머스 문제 링크 난이도 : level 3 해결 방법 노드 사이에서 관계를 가지고 있으므로 자료 구조는 그래프를 사용하고 탐색하는 방법은 BFS 혹은 DFS 를 사용하여 풀 수 있습니다. 해당 문제에서는 모든 공항을 방문해야 하므로 DFS 를 사용했습니다. 소스 코드 function solution(tickets) { let answer = []; const visitedList = []; const visited = new Array(tickets.length); const vAirport = []; visited.fill(false); const dfs = function(tickets, cur, depth){ // 종료조건 if(depth == tickets.length){ vAir..

문제 정보 프로그래머스 문제 링크 난이도 : level 3 해결 방법 노드 사이에서 관계를 가지고 있으므로 자료 구조는 그래프를 사용하고 탐색하는 방법은 BFS 혹은 DFS 를 사용하여 풀 수 있습니다. 해당 문제에서는 단어를 변환할 수 있는 최소 단계를 구해야 하므로 BFS 를 사용합니다. DFS 를 사용할 경우 최소 단계를 발견하더라도 다른 경로를 모두 탐색해야 최소 단계임을 보장할 수 있기 때문에 비효율적이기 때문 입니다. 소스 코드 function solution(begin, target, words) { let answer = 0; // target 이 words 에 없는 경우 if(!words.includes(target)){ return answer; } // 방문여부 초기화 const vi..

1. DFS, BFS 그래프 탐색을 위해서는 DFS ( Depth-First Search, 깊이 우선 탐색 ), BFS ( Breadth-First Search, 너비 우선 탐색 ) 를 사용한다. 2. 그래프와 트리 비교 그래프는 노드와 노드를 잇는 (없을 수도 있지만) 간선을 가진 자료구조이며, 그 중 방향성이 있는 비순환 그래프가 트리이다. 3. DFS, BFS 시간복잡도 인접 리스트로 표현된 그래프 : O(N+E) 인접 행렬로 표현된 그래프 : O(N^2) 참고 : [알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)