https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 풀이 한 정점에서 다른 정점으로 최단경로로 이동할 때 가장 먼저 거쳐야 하는 정점을 구해야 하기 때문에 그래프 최단거리 알고리즘(다익스트라)을 응용하여 풀었다. 다익스트라 알고리즘을 진행할 때, 각 엣지에 먼저 거치는 정점도 저장하기 위해 Edge 클래스에 int형 멤버변수 startV를 추가했고, 이후 PQ에 엣지를 추가할 때 이전 엣지의 startV를 세팅하여 저장하는 로직을 추가하였다. static ..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 풀이 기본적인 그래프 최단거리 문제다. 그래프 최단거리 알고리즘으로는 다익스트라, 벨만포드, 플로이드-와샬이 있다. 1

1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 최단 경로를 구하는 문제지만, 특정 정점을 지나는 최단 경로의 길이를 구해야 한다. 1번 정점 -> N번 정점의 최단 경로를 구해야 하는데, 두 정점 v1, v2를 거치는 최단 경로를 구해야 한다. 즉 위 조건을 만족하는 1번 정점 -> N번 정점의 최단 경로는 두가지가 있다. 1. 1 -> v1 -> v2 -> N 2. 1 -> v2 -> v1 -> N 그렇다면 각 정점부터 정점까지의 최단 경로를 구해서, 모든..

1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 그래프 최단 경로를 구하는 다익스트라 알고리즘을 사용하여 푸는 문제다. 인접리스트, PriorityQueue, 각 정점까지의 최단 경로를 저장하는 dis 배열을 사용하여 풀었으며 자세한 풀이는 이전에 풀었던 문제와 같기 때문에 설명은 생략하겠다. [프로그래머스] Lv.2 : 배달 (그래프 최단 경로 알고리즘) - 자바[Java] [프로그래머스] Lv.2 : 배달 (그래프 최단 경로 알고리즘) - 자바[Java] http..

https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이1 : 다익스트라 - 순차 탐색, 인접 배열 최단 경로 알고리즘을 사용하여 1번 마을부터 각 마을까지의 최단 시간(경로)를 구해야 한다. 최단 경로 알고리즘이란 주어진 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다. 대표적인 최단 경로 알고리즘은 3가지가 있다. 다익스트라 알고리즘 (default, 가중치가 모두 양수 = 음수X) 벨만 포드 알고리즘 (dista..