N

https://leetcode.com/problems/path-with-maximum-probability/ Path with Maximum Probability - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 다익스트라 알고리즘. start에서 end까지 갈 수 있는 확률 중 가장 높은 path를 찾아야 한다. 일반적인 다익스트라처럼 큐를 이용. 우선 n 크기의 배열을 선언하고, 빈 배열로 초기화 하여 graph라는 이름으로 선언. 각 지점까지의 거리를 나타..

https://leetcode.com/problems/cheapest-flights-within-k-stops/ Cheapest Flights Within K Stops - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 다익스트라 알고리즘 활용. 우선 graph라는 이름의 n 크기의 배열을 선언하여 []로 초기화. 또한, n 크기의 dist 배열도 선언하여 infinity로 초기화. flights를 순회하여 그래프를 그려준다. 단방향이기 때문에 from, to,..

https://leetcode.com/problems/path-with-minimum-effort/ Path With Minimum Effort - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 우선순위큐로를 이용한 풀이. MinHeap으로 우선순위 큐를 구현. BFS 방식과 비슷하게 PriorityQueue에 방문할 좌표와 minimum effort를 넣으면 된다. pq에 push하면 알아서 minHeap으로 정렬해주기 때문에 방문할 좌표와 방문 여부를 확인해..

https://leetcode.com/problems/network-delay-time/ Network Delay Time - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 다익스트라 알고리즘 활용. 우선 주어진 times 배열을 그래프로 나타내기 위해 n + 1 크기의 graph 2차원 배열을 선언. 또한, 노드 간 걸리는 시간을 dist 배열에 저장하기 위해 n + 1 크기의 1차원 배열을 선언하여 Infinity로 초기화한다. times를 순회하면서 노드를..

https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 다익스트라를 이용한 문제풀이. 우선 road에 담겨있는 정보(시작 마을, 도착 마을, 비용)를 담을 수 있는 graph를 선언. dist는 각 마을까지 갈 수 있는 최소 비용을 저장하는 배열이다. queue는 다익스트라를 진행할 때 사용하는 배열. for문으로 road에 담겨져 있는 정보를 graph에 담는다. start 번호로 시작하는..

문제 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익) 어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다. 이 듀오는 대체 어디로 가고 있는 것일까? 예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하..

문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지..

문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다. 출력 첫째 줄부터 V개의 줄..