본문 바로가기
728x90

최단 경로

 (6)
[백준] 1504번 특정한 최단 경로 [Python] - 데이크스트라 무방향 그래프에 1번에서 u, v 노드를 거쳐서 N번 노드로 가는 최단 경로의 길이를 구하는 문제 1-u-v-N, 1-v-u-N 의 규칙만 지켜서 최단 경로를 구하면 된다. 불가능 할 때, -1을 출력한다. 더보기 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동..
[백준] 1865번 웜홀 [Python] - 벨만 포드 테스트 케이스의 개수만큼 아래 주어진 정보로 답을 구해야 한다. N개의 지점에 M개의 도로$($무방향$)$와 W개의 웜홀$($단방향$)$이 있다. 도로와 웜홀은 시작 위치, 도착 위치, 소요 시간으로 주어진다. 소요 시간은 0 이상, 10,000 이하인데, 웜홀은 도로와 다르게 소요 시간만큼 시간이 줄어든다. - 음수처럼 생각하면 쉽다. 각 테스트 케이스에서 처음 위치로 되돌아 올 때, 시간이 과거로 갈 수 있다면 YES, 불가능하면 NO를 출력하는 문제 TC N, M, W 도로 정보 M개 웜홀 정보 W개 x TC 수만큼 반복 더보기 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. $(단 도로는 방향이 없으..
[백준] 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줄까지 다음과 같은 버스의 정보가 주..

티스토리툴바