# Shortest Path

hyeon3356

Topological Sorting (위상 정렬) DAG에서 최단경로를 찾기 위해서는 먼저 위상정렬을 수행하여 topological order를 찾아야 한다. 위상 정렬을 하는 방법은 아래 포스트에 정리해놓았다. https://velog.io/@hyeon3356/DAG-%EC%97%90%EC%84%9C-Shortest-Path-%EC%B0%BE%EA%B8%B0 최단 거리 찾기 위와 같은 DAG 가 존재하고 모든 간선의 weight 는 1이라고 한다. topological order 가 A -> B -> C -> D -> E -> F 라는 것을 이미 구했다고 하자. 시작점 A로부터 모든 정점들의 최단 경로를 구해보자. step 0 먼저 최단 경로를 저장할 배열을 선언해야 한다. A는

morion002

문제 문제 설명 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라. 제한 사항 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝

choihjin

Input : directed graph G = (V, E) with weight function w : E → R Determine the path p with minimum weight from source to destination Weight w(p) of path p : sum of edge weights on path p shortest-path weight u to v : Variants Single-source shortest path : find shortest paths from a given source vertex s $\in$ V to every vertex v $\in$ V

longbright_choi

Shortest Path 기본 말 그대로 가장 짧은 경로를 찾는 알고리즘. ‘길 찾기’ 문제라고도 불림 다양한 유형의 알고리즘이 존재하며, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있음 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 상황 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 상황 대표적인 알고리즘 3가지 : 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘 다익스트라 알고리즘(Dijkstra Algorithm) Dijkstra 기본 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 상황 ‘음의 간선’ 이 없을 때 정상적으로 동작함 매번 ‘가장 비용이 적은 노드’를 선택해서 임의의 과정을 반복하기 때문에 기본적으로 그리디 알고리즘으로

longbright_choi

💡 문제 💬 입출력 예시 📌 풀이(소스코드) 📄 해설 무향 그래프에 대한 다익스트라 알고리즘을 수행하고, 최단 경로가 갱신될때마다, 그 경로를 저장한다는 아이디어를 얻으면 해결이 가능한 문제 최단 거리의 경로를 저장하기 위해 1차원 배열인 path 를 사용하였으며, 각각의 인덱스에는

longbright_choi

💡 문제 💬 입출력 예시 📌 풀이(소스코드) 📄 해설 다익스트라 알고리즘을 수행하고, 감염 개수를 파악하는 것과, 최단 거리 테이블의 최댓값이 마지막으로 감염된 시간이라는 접근을 하면 풀 수 있는 문제 결과값을 얻는 부분이 꼭 위와 같이 수행되지 않고, 아래와 같이 다익스트라 알고리즘 수행 중에 처리가 되어도 됨 참고로 거리의 최댓값이 100,000 이라고 해서, INF 의 값을 100,001 로 초기화 할 경우 틀리게 됨 (입력에서의 거리가 100,000 까지만

longbright_choi

💡 문제 💬 입출력 예시 📌 풀이(소스코드) 📄 해설 바로 어제 풀었던 백준의 구슬 찾기 문제와 동일한 유형의 문제 a 가 b 보다 크다는 것을 나타내기 위해 최단경로 테이블 d 의 값을 da = 1 로 초기화하고, 플로이드 워셜 알고리즘을 수행 -> `init() ~ f

longbright_choi

💡 문제 💬 입출력 예시 📌 풀이(소스코드) 📄 해설 DFS 로도 풀 수 있는 문제라고함, 플로이드 워셜로 해결하였음 플로이드 워셜 알고리즘 수행을 위해 입력 시 큰구슬을 1로 초기화하고, 이외의 지점은 전부 INF 로 초기화 플로이드 워셜 알고리즘을 수행하여 최단 경로 테이블을

longbright_choi

💡 문제 💬 입출력 예시 📌 풀이(소스코드) 📄 해설 최단경로 알고리즘 중 플로이드 워셜 알고리즘을 수행

longbright_choi

💡 문제 💬 입출력 예시 📌 풀이(소스코드) 📄 해설 모든 쌍의 최단 경로를 구해야하므로 플로이드 워셜 알고리즘을 적용하여 푸는 문제 플로이드 워셜 알고리즘 수행을 위해 DP 테이블을 적당히 큰 값인 INF로 초기화하고, 자기 자신으로 가는 곳인 i == j 인 경우 0 으로 초기

longbright_choi

💡 문제 💬 입출력 예시 📌 풀이(소스코드) 📄 해설 우선순위 큐를 이용한 다익스트라 알고리즘을 적용하면 쉽게 풀리는 문제 2차원 최소비용 배열 cost 는 INF 로 초기화하고, 다익스트라 알고리즘을 수행 이때 최소비용의 갱신은 현재까지의 최소 비용 + 다음칸의 비용 과

junnkk

최단 경로 가장 빠르게 도달하는 방법 다익스트라 최단 경로 알고리즘 방법1. 간단한 다익스트라 알고리즘 방법2. 개선된 다익스트라 알고리즘 플로이드 워셜 알고리즘 최단 경로 가장 빠르게 도달하는 방법 다익스트라 최단 경로 알고리즘 방법1. 간단한 다익스트라 알고리즘 시간 복잡도 O(V^2) V는 노드 개수 방법2. 개선된 다익스트라 알고리즘 시간 복잡도 O(ElogV) E는 간선의 개수, V는 노드의 개수 힙 자료구조 이용 -> 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있다. 힙 Heqp 자료구조 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나 우선순위 큐 -> 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다.

longbright_choi

💡 문제 어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어 있어야 한다. 예를 들어 X에서 Y로 향하는 통로는 있지만, Y에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다. 또한 통로를 거쳐 메시지를 보낼 때는 일정 시간이 소요된다. 어느 날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메시지를 보내고자 한다. 메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌을 때, 도시 C에서 보낸 메시지를 받게 되는 도시의 개수는 총 몇 개이며 도시들이 모두 메시지를 받는 데까지 걸리는 시간은 얼마인지 계산하는 프로그램을 작성하시오.

longbright_choi

💡 문제 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다. 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 한다. 미래 도시에서 특정 회사에 도착하기 위한 방법은 회사끼리 연결되어 있는 도로를 이용하는 방법이 유일하다. 또한 연결된 2개의 회사는 양방향으로 이동할 수 있다. 공중 미래 도시에서 특정 회사와 다른 회사가 도로로 연결되어 있다면, 정확히 1만큼의 시간으로 이동할 수 있다. 또한 오늘 방문 판매원 A는 기대하던 소개팅에도 참석하고자 한다. 소개팅의 상대는 K번 회사에 존재한다. 방문 판매원 A는 X번 회사에 가서 물건을 판매하기 전에 먼저 소개팅 상대의 회사에 찾아가서 함께 커피를 마실 예정이다. 따라서 방문 판매원 A는 1번 회사에서 출발하여 K번 회사를 방문한 뒤에 X번 회사로 가는 것이 목표다. 이때 방문 판매원 A는 가능한 한 빠르게 이동하고자 한다. 방

sun202x

사이트: HackerRank 난이도: 미디움 분류: Search 문제 일반적인 체스의 나이트는 두칸 수직, 수평이동 하고 옆 또는 위아래로 한 칸씩 움직이는 이동경로를 보여준다. 이 나이트의 움직임을 커스터마이징하여 Red Knight라는 유닛을 하나 만들었고, 해당 유닛의 이동경로는 아래와 같다 시작 위치와 도착해야할 위치가 주어졌을 때, 최단 경로로 이동한 경로를 출력하고 도착할 수 없다면 Impossible을 반환하라. 1. 나의 풀이 최단 경로를 찾는 문제이기 때문에 bfs를 사용하여 해결하였다. 다만 이동한 경로를 알아내기 위해 queue에서 소비된 노드 정보들이 필요했고, 그것을 기록하여 마지막에 이동 경로를 찾아내 반환하도록 하였다. 2. 다른사람의 풀이 바로 풀 수 있었던 문제들은 지금은 생략하고 추후 더 효율적인 문제 풀이법을 찾아보도록 하겠다.

yoopark

백준 11404번. 플로이드에 대한 풀이를 Floyd-Warshall Algorithm의 스니펫 느낌으로 작성. 모든 정점에서 모든 정점까지의 Shortest Path(최단 경로) 를 구할 때 사용. (단, 가중치는 모두 양수여야 함.)

yoopark

백준 11657번. 타임머신에 대한 풀이를 Bellman-Ford Algorithm의 스니펫 느낌으로 작성. 한 정점에서 다른 모든 정점까지의 Shortest Path(최단 경로) 를 구할 때 사용. (가중치가 음수여도 됨.)

yoopark

백준 1753번. 최단경로에 대한 풀이를 Dijkstra's Algorithm의 스니펫 느낌으로 작성. 한 정점에서 다른 모든 정점까지의 Shortest Path(최단 경로) 를 구할 때 사용. (단, 가중치는 모두 양수여야 함.)

yoopark

오늘의 한 마디 > 내가 원래 짜놨던 벨만-포드 알고리즘 스니펫이 틀렸었네..? Baekjoon 문제 링크 현재 백준 문제집: 단기간 성장을 풀고 있습니다. 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다. 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M

yoopark

오늘의 한 마디 > 진짜 빡구현해야 하는 문제가 있는 반면, > 이번 문제처럼 알고 나면 정말 허무할 정도로 간단한 경우가 있다. Baekjoon 문제 링크 현재 백준 문제집: 단기간 성장을 풀고 있습니다. 문제 V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자. 당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다. 단, 당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다. 도로의 정보가 주어졌을 때, **도로의 길이의 합이