문제 정보 프로그래머스 문제 링크 난이도 : level 3 해결 방법 맨 처음에는 그래프를 순회하면서 순위를 매기는 방법을 생각했었는데 다른 node 로 이동할 때마다 순위를 명확히 체크할 수 있다는 보장이 없어서 각 node 하나하나 마다 순위를 확정할 수 있는지 체크하기로 했습니다. 주어진 예제를 확인해보니 순위를 확정할 수 있는 node 는 아래 그림과 같이 자신보다 순위가 위 이거나 아래인 다른 모든 node 들을 찾았을 때 였습니다. 그래서 upperVisited 라는 자신보다 상위 순위에 있는 node 목록과 lowerVisited 라는 자신보다 하위 순위에 있는 node 목록을 node 마다 각각 생성했습니다. 이 두개의 길이가 본인을 제외한 전체 노드 갯수인 n - 1 이 될 경우 순위를 ..

문제 정보 프로그래머스 문제 링크 난이도 : level 3 해결 방법 최단 경로로 이동했을 때 가장 멀리 떨어진 노드를 구해야 해서 BFS 알고리즘을 사용했습니다. BFS 는 다음에 탐색할 정보를 queue 에 넣기 때문에 depth 의 경우 shortestList 에 따로 저장하고 현재 노드인 curNodeNum 의 depth 에 1 을 더한 값을 nextNode 의 shortestList 에 추가했습니다. BFS 의 특성상 depth 는 증가만 하기 때문에 이미 최단경로의 depth 를 구한 경우에는 저장하지 않도록 했습니다. 최단경로를 모두 탐색하고 최종적으로 shortestList 에 있는 최대값의 개수를 counting 했습니다. 소스 코드 function solution(n, edge) { l..

문제 정보 프로그래머스 문제 링크 난이도 : 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..

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