0710_TIL

🎄오늘 한 일

✔️ 1.  이것이 코딩테스트다_최단거리 파트 학습

• 최단거리를 구하는 알고리즘은 크게 다익스트라 알고리즘과 플로이드워셜 알고리즘이 있다.
• 다익스트라 알고리즘은 출발노드가 정해졌을 때, 출발노드에서 다른 모든 노드까지의 최단경로를 구한다.
  다익스트라 알고리즘은 본질적으로 그리디알고리즘으로, 현재 노드에서의 최선의 노드를 선택한다.
• 플로이드워셜 알고리즘은 모든지점에서의 다른 모든 지점까지의 최단경로를 모두 구해야하는 경우 사용한다. (2차원행렬꼴)
  플로이드 워셜 알고리즘은 점화식을 통한 DP에 가깝다.
  Distance(a,b)  = Min( Distance(a,b) , Distance(a,k) + Distance(k,b) ) 의 점화식을 활용한다.

✔️ 2.  최단거리 알고리즘을 활용한 문제 풀어보기

• 이코테_전보 (다익스트라 알고리즘)
• 이코테_미래도시 (플로이드워셜 알고리즘)
• 프로그래머스_배달 (다익스트라 알고리즘)

 

🎄기억할 것

다익스트라 알고리즘을 활용한 최단거리 구현 과정

: 시작노드가 명확하고, 시작노드로 부터 다른 노드까지의 최단거리를 구해야할 때 사용

핵심동작원리

1. 출발노드를 설정하고, 최단거리 테이블을 초기화한다.
2. 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다.
3. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하고, 현재 최단거리와 비교하여 최단거리 테이블을 갱신한다.
4. 2-3과정을 N(노드의 개수)만큼 반복한다.

세부 코드 구현 탬플릿

1. 초기값, 변수 세팅
   1.1 인접행렬이 없다면 생성한다. (graph)
   1.2. 방문여부를 관리하는 1차원 배열을 생성한다.  -모든 초기값 false (visited)
         visited[start] = true (초기값 방문 설정하기) 
   1.3 최단거리를 관리하는 1차원 배열을 생성한다. -모든 초기값 Infinity(987,654,321) (distance)
        graph[start][i]를 순회하며, start노드와 연결된 노드들의 거리를 distance의 입력한다.
2. 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드 선택
   2.1 가장짧은 노드를 선택 ( get_smallest_node() )
    노드개수 만큼 순회하며 ( !visited[i] && distance[i] < minValue ) 경우 idx를 기록하여 최종 최단거리노드(idx)를 리턴한다.
   2.2 선택노드 방문처리
    visited[now] = true; 
3. 해당 노드를 거쳐 다른 노드로 갈 때의 거리와, 현재 최단거리를 비교하며, 최단거리 테이블 갱신
   cost = distance[now] + graph[now][j] 
   와 distance[j] 를 비교하여 더 작은 값으로 distance를 갱신한다.
4. 2-3의 과정을 (전체노드개수-1 )번 반복한다.

function dijkstra_basic(N, m, start, adjList) {
  let graph  = ...
  let visited = Array(N + 1).fill(false);
  let distance = Array(N + 1).fill(Infinity);

  // 방문하지 않은 노드 중, 가장 최단 거리가 짧은 노드번호를 반환
  function get_smallest_node() {
    let min = Infinity;
    let smallest_idx = 0;
    for (let i = 1; i < N + 1; i++) {
      if (distance[i] < min && !visited[i]) {
        min = distance[i];
        smallest_idx = i;
      }
    }
    return smallest_idx;
  }

  function dijkstra(start) {
    distance[start] = 0;
    visited[start] = true;
    //1.2 시작노드에서의 distance 설정
    for (let i = 1; i < N + 1; i++) {
      if (start === i) continue;
      distance[i] = graph[start][i];
    }

    // 나머지 노드를 짧은 거리순으로 방문하며, distance 갱신
    for (let i = 0; i < N - 1; i++) {
      let now = get_smallest_node();
      visited[now] = true;

      // now(방문해야하는 노드)를 거쳐 다른 노드에 갈때 거리와 , 현재 거리배열과 비교하며 갱신
      for (let j = 1; j < graph[now].length; j++) {
        let cost = distance[now] + graph[now][j];
        if (cost < distance[j]) {
          distance[j] = cost;
        }
      }
    }
  }
  dijkstra(start);
  return distance;
}

시간복잡도

• 시간복잡도는 O(N^2)이다.
  N개의 노드에서 최단거리르 확인해야하며, 최단거리를 갱신할 때 N번의 선형탐색이 이루어지기 때문이다.

실전문제풀이 

📎 배달

 

플로이드워셜 알고리즘을 이용한 최단거리 구현

: 모든지점에서 다른 모든 지점까지의 최단경로를 모두 구해야할 때 사용

 

핵심동작원리

1. 인접행렬 그래프 생성하기
   1.1 자기자신노드로의 거리는 0
   1.2 주어진 간선을 순회하며 그래프 완성하기
2. 3중반복문으로 다음노드가 k일때, 모든 경우의 수 구하기
   graph[from][to] = Math.min ( graph[from][to] , graph[from][k] + graph[k][to]
3. 소스코드

function solution(N, M, edges) {
  //초가 그래프 생성
  let graph = Array(N + 1)
    .fill(0)
    .map(() => Array(N + 1).fill(Infinity));

  // 자기자신으로의 거리는 0으로 바꾸어줌
  for (let i = 1; i < N + 1; i++) {
    for (let j = 1; j < N + 1; j++) {
      if (i === j) graph[i][j] = 0;
    }
  }
  // 각 노드간의 거리르 graph에 기록한다.
  for (let i = 0; i < M; i++) {
    let [from, to, value] = edges[i];
    graph[from][to] = value;
  }

  // 2.노드를 순회하며, 해당 노드를 거쳐갈 경우의 최단거리 갱신가능성을 체크함
  for (let cur = 1; cur < N + 1; cur++) {
    for (let from = 1; from < N + 1; from++) {
      for (let to = 1; to < N + 1; to++) {
        graph[from][to] = Math.min(
          graph[from][to],
          graph[from][cur] + graph[cur][to]
        );
      }
    }
  }
  return graph;
}

<-> 다익스트라
방문하지않은 노드 중 최단거리 갖는 노드를 찾는 다익스트라와 달리, 이러한 과정이 없고 현재 노드에서 갈 수 있는 모든 노드에 O(N^2)연산 수행

 

시간복잡도

N번의 노트탐색 + 노드탐색시 O(N^2)으로 최소거리테이블 갱신하므로, O(N^3)이다.