- Today
- Total
목록다익스트라 (23)
개발하는 고라니
2276번: 물 채우기 첫째 줄에 M, N(1≤N, M≤300)이 주어진다. 다음 M개의 줄에는 N개의 자연수로 각 칸의 높이가 주어진다. 각각의 높이는 1,000,000,000를 넘지 않는다. www.acmicpc.net # 문제 N×M 크기의 물통이 있다. 이 물통의 각 칸은 높이가 다를 수도 있다. 이와 같은 물통에 물을 부었을 때, 담을 수 있는 물의 최대량을 계산하는 프로그램을 작성하시오. 물통의 테두리도 높이가 다를 수 있고, 테두리가 물통의 안쪽보다 높이가 낮을 수도 있다. 왼쪽 표는 물통의 높이를 나타낸 것이고, 오른쪽은 각 칸에 담은 물의 양을 나타낸 것이다. 이 경우가 답이 12로 최대인 경우가 된다. # 입력 첫째 줄에 M, N(1≤N, M≤300)이 주어진다. 다음 M개의 줄에는 N..
13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net # 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장..
1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net # 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에..
1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net # 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다...
1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net # 문제 알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다. 알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을..
[알고리즘] 다익스트라(Dijkstra) 알고리즘 최단 경로 최단 경로 문제에서 입력 그래프의 유형은 크게 두 가지이다. 모든 간선 가중치가 음이 아닌 경우 음의 가중치가 존재하는 경우 음의 가중치를 허용하지 않는 경우 다익스트라(Dijkstra) dev-gorany.tistory.com 이전 포스팅의 다익스트라 알고리즘을 구현한 코드는 O(N^2)의 시간 복잡도를 갖는다. 모든 정점을 한 번씩 순회하는 N번의 loop와 그 안에서 distance[i]의 가장 작은 값의 인덱스를 찾는 N번의 loop가 호출되었다. 단순히 다익스트라 알고리즘을 구현하고 사용하는데에는 코드도 직관적이고 다른 자료구조도 안쓰여서 쉽게 쓸 수 있으나 문제를 풀거나, 서비스에 적용해야 할 때는 문제가 될 여지가 충분하다. 이를 ..
최단 경로 최단 경로 문제에서 입력 그래프의 유형은 크게 두 가지이다. 모든 간선 가중치가 음이 아닌 경우 음의 가중치가 존재하는 경우 음의 가중치를 허용하지 않는 경우 다익스트라(Dijkstra) 알고리즘으로 이 유형의 문제를 푼다. 음의 가중치를 허용하는 경우 벨만-포드 알고리즘으로 이 유형의 문제를 푼다. 음의 가중치는 허용하지만 가중치 합이 음수인 사이클은 절대 허용하지 않는다. 음의 사이클이 있으면 해당 사이클을 몇번이고 돌아 경로의 가중치 합을 무한정 낮출 수 있기 때문에 최단 경로 문제 자체가 성립하지 않는다. Dijkstra 알고리즘 다익스트라 알고리즘은 하나의 시작 정점에서 다른 모든 정점까지 최단 경로를 구한다. 다만 이 때 음의 가중치를 갖는 간선은 허용하지 않는다. 임의의 두 정점 ..