데이크스트라 (6) 썸네일형 리스트형 [백준] 14938번 서강그라운드 [Python] - 플로이드 워셜, 데이크스트라 지역의 개수 n, 수색범위 m, 길의 개수 r에 대해서 각 지역마다 주어진 아이템 수와 지역을 연결하는 길의 길이가 주어질때, 얻을 수 있는 최대 아이템 개수를 구하는 문제 $($수색 범위를 넘어가는 먼 지역은 탐색할 수 없음$)$ 더보기 문제 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 프로그램을.. [백준] 1504번 특정한 최단 경로 [Python] - 데이크스트라 무방향 그래프에 1번에서 u, v 노드를 거쳐서 N번 노드로 가는 최단 경로의 길이를 구하는 문제 1-u-v-N, 1-v-u-N 의 규칙만 지켜서 최단 경로를 구하면 된다. 불가능 할 때, -1을 출력한다. 더보기 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동.. [백준] 1238번 파티 [Python] - 데이크스트라 N개의 마을마다 한 명의 학생이 있고, 어느 날 X번 마을에 모여서 파티를 한다. M개의 단방향 도로가 있고, 시작 도시 A, 도착 도시 B, 소요시간 T가 정보로 주어진다. 각 학생이 자신의 마을에서 X 마을에 모여 파티를 참석하고 자신의 마을로 다시 돌아오는 데 드는 최단 이동 소요시간 중 최대 값을 구하는 문제 더보기 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X $(1 ≤ X ≤ N)$번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 $T_{i}$$(1 ≤ Ti ≤ 100)$의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만.. [백준] 1753번 최단경로 [Python] - 데이크스트라 방향 그래프의 정점 V개에 대해서 간선 E개의 정보가 시작점, 도착점, 가중치 순서로 주어질 때, 시작 정점 K에서 출발해서 첫번재 노드 부터 V 번째 노드까지의 최단 경로의 가중치를 구하는 문제 자기 자신은 0, 경로가 존재하지 않는 경우에는 INF 출력 더보기 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. $(1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000)$ 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각.. [백준] 13549번 숨바꼭질 3 [Python] - 데이크스트라 N을 아래 연산을 통해서 K로 바꾸는 데 걸리는 시간을 구하는 문제 연산 : 소요 시간 +1 또는 -1 : 1초 x2$($2배$)$ : 0초 더보기 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N$(0 ≤ N ≤ 100,000)$에 있고, 동생은 점 K$(0 ≤ K ≤ 100,000)$에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 .. [백준] 1916번 최소비용 구하기 [Python] - 그래프 이론 도시의 수: N, 버스의 수: M와 정보: $($A -> B, 버스 비용$)$, 출발 도시: S, 도착 도시: E에 대한 정보가 주어질 때, 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 구하는 문제 더보기 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N$(1 ≤ N ≤ 1,000)$이 주어지고 둘째 줄에는 버스의 개수 M$(1 ≤ M ≤ 100,000)$이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주.. 이전 1 다음
