Dot Dot Line Dot

title: Programmers - 부대복귀 date: 2022-10-25 tags: Algorithm Graph Dijkstra https://school.programmers.co.kr/learn/courses/30/lessons/132266 문제 요약 그래프가 주어지며, 출발 지점의 리스트와 하나의 도착 지점이 주어진다. 각 출발 지점에서 도착 지점까지 가는 경로의 최소 길이를 vector에 넣어 return한다. 경로가 없다면 -1을 넣는다. 문제 풀이 Node의 개수는 최대 100K이며, O(n^2) 이상이라면 TLE가 발생할 것이다. 출발 지점이 모두 달라 Bellman Ford Algorithm을 사용할 수 없다. 하지만 도착 지점이 하나이기에, 이를 역으로 생각하면 도착 지점에서 각 지점..

title: Programmers - 배달 date: 2022-06-21 tags: Algorithm Graph Dijkstra https://programmers.co.kr/learn/courses/30/lessons/12978 문제 요약 주어진 그래프에서 root 노드로부터 K 가중치 내로 이동 가능한 노드의 수를 구하여 return한다. 문제 풀이 전형적인 Dijkstra Graph 문제이다. 주어진 그래프를 인접행렬로 변환한 후, N-1번 거리를 갱신하여 root로부터 모든 노드로 가는 거리가 K 이하인 노드의 개수를 구한다. 갱신이 이루어지지 않을 때 갱신을 중단하여도 되지만, 최대 갱신 횟수는 N-1번이다. 중단 조건 구현이 귀찮아서 N-1번 갱신하였다. 가중치에 -가 존재한다면 Floyd-W..