본문 바로가기

데이크스트라9

[백준] 12913: 매직 포션 - JAVA https://www.acmicpc.net/problem/12913 풀이0번 도시에서 1번 도시까지 가장 빠른 시간에 가야 한다. 포션을 마실 수 있는데 마시게 되면 한 도시에서 다른 도시로 이동하는데 드는 시간을 반으로 줄일 수 있다. n개의 도시, 포션 사용 가능 개수 k가 주어진다. 즉, 이차원배열을 `dist[n][k + 1]`로 선언하여 포션을 사용한 개수마다 체크해주어야 한다. 우선 도시마다 걸리는 시간이 모두 양수이기 때문에 0번 도시부터 모든 도시까지 최소 시간을 구할 수 있는 다익스트라 알고리즘을 적용했다. 다음 도시로 이동할 때 포션을 쓰지 않는 경우, 쓰는 경우를 나눠 진행해야 한다. 포션을 쓰는 경우는 현재 도시에 오는데 쓰인 포션의 개수가 k보다 작은 경우에만 가능하다.  메모리:.. 2024. 9. 10.
[백준] 10282: 해킹 - JAVA https://www.acmicpc.net/problem/10282 풀이문제풀고 바로 블로그에 써야하는데 게을러서 늦게 쓰는 풀이.. a가 b를 의존하고 있다면, b가 감염되고 일정 시간 뒤 a도 감염된다. 따라서, b에서 a로 가는 경로가 있다고 생각했다. 이런 관계들을 `ArrayList`에 담아주었다. 감염된 컴퓨터 c부터 시작하여 다익스트라 알고리즘을 통해 경로를 따라갔다. 다익스트라 알고리즘은 최단 경로를 알려주는데, b에서 a로 감염될 때 걸리는 시간을 가중치로 두고 진행했다. 최종적으로 dist배열의 값이 INF가 아닌것들을 세주면 끝.   메모리: 148832KB시간: 784ms언어: Java 11import java.io.*;import java.util.*;public class Mai.. 2024. 7. 18.
[백준] 24042: 횡단보도 - JAVA https://www.acmicpc.net/problem/24042 풀이1 ~ N 까지 영역이 있고 각 영역을 잇는 횡단보도를 통해 건널 수 있다. M개의 횡단보도가 켜지는 순서대로 주어진다. 즉, 첫번째 횡단보도는 0, M, 2M... 시간에 켜지고, 두번쨰 횡단보도는 1, M + 1, 2M + 1... 시간에 켜진다. 켜지는 시간을 가중치로하여 다익스트라 알고리즘을 수행하면 된다. 현재 시간보다 다음 건널 횡단보도에 적힌 시간이 작다면 더 커질때까지 M을 더해야 한다. `long nextCost = curr.cost + ((next.cost - curr.cost) % M + M) % M + 1;` 위 식으로 계산할 수 있었다.  메모리: 222712KB시간: 1292ms언어: Java 11import.. 2024. 5. 18.
[백준] 20160: 야쿠르트 아줌마 야쿠르트 주세요 - JAVA https://www.acmicpc.net/problem/20160 풀이야쿠르트 아줌마의 판매 경로 10개가 주어진다. 아줌마가 해당 위치에 도착하기 전에 가있어야 아쿠르트를 살 수 있다. 먼저 내 시작위치로부터 각 위치까지 얼마나 걸리는지 다익스트라를 통해 구했다. 야쿠르트 아줌마의 시간을 누적해가면서 경로대로 움직였다. 아줌마의 현재위치부터 다익스트라를 통해 다음 위치까지 시간을 구했고, 해당 시간이 `Integer.MAX_VALUE`이면 그 다음 위치를 보는 식으로 구현했다. `ans`를 갱신하여 정점의 번호가 가장 낮은 것이 정답.  메모리: 68732KB시간: 920ms언어: Java 11import java.util.*;import java.io.*;public class Main { s.. 2024. 5. 18.
[백준] 5972: 택배 배송 - JAVA https://www.acmicpc.net/problem/5972 풀이1부터 N까지 이동해야하는데 길마다 지불해야할 비용이 있다. 즉, 다익스트라 알고리즘을 이용해 최솟값을 구해준다. ArrayList로 연결된 지점과 비용을 저장하고 dist배열을 만들고 최댓값으로 초기화해준다. 현재칸과 연결된 칸의 비용을 보면서 dist[다음칸]이 (`dist[현재칸] + 비용`)보다 크다면 더 작은 비용으로 이동할 수 있다는 것이므로 갱신해준다.  메모리: 41024KB시간: 484ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Node implements Comparable { int v; .. 2024. 5. 17.
[백준] 9370: 미확인 도착지 - JAVA https://www.acmicpc.net/problem/9370 풀이목적지까지 최단경로에 (g-h)나 (h-g) 도로를 거치는지 확인하는 문제이다. 목적지를 t, 출발지를 s라고 한다면 (s-t)의 거리가 (s-g) + (g-h) + (h-t), (s-h) + (h-g) + (g-t) 두 거리 중 작은 값과 같다면 g-h 도로를 지났다고 확인할 수 있다. 따라서 다익스트라 알고리즘을 사용하여 s부터의 거리 배열, g부터의 거리, h부터의 거리 3개의 배엻을 구한다. (s-t) 거리가 다른 두 거리 중 작은 값과 같다면 출력한다.  메모리: 63248KB시간: 676ms언어: Java 11import java.util.*;import java.io.*;public class Main { static.. 2024. 5. 17.
[백준] 6087: 레이저 통신 - JAVA https://www.acmicpc.net/problem/6087 풀이목적지까지 가야하는데 방향전환을 하려면 거울을 써야한다. 거울을 최소로 쓰면서 목적지에 도달해야 한다. 거울을 쓴 개수가 적은것 부터 탐색하기 위해 우선순위큐를 사용했다. 방문처리를 쓴 거울의 개수로 하는 int 이차원배열로 했었는데 메모리초과가 발생했다. 삼차원배열로 방향까지 체크를 해서 어느 방향일때 최소인지 확인하였더니 해결됐다.  메모리: 15720KB시간: 172ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Node implements Comparable { int r; int c; i.. 2024. 5. 17.
[백준] 14461: 소가 길을 건너간 이유 7 - JAVA https://www.acmicpc.net/problem/14461 풀이격자로 이루어진 땅을 건너가야하는데 세칸을 이동할 때 마다 격자에 써있는 만큼의 풀을 먹어야 한다. 한칸을 이동할 때는 T만큼의 비용이 든다. 격자 칸마다 다른 가중치가 있다. 즉, 다익스트라를 이용해 문제를 풀면 된다. 3칸을 이동하는 방법은 ABA 처럼 갔던 칸에 다시 방문하는 방법이 있고, ABC처럼 다른 칸에 갈 수도 있다. 이러한 방법들을 적어보니 16가지가 된다. 이차원 배열로 만들어 사용했다.static int[][] vector = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }, { 3, 0 }, { -3, 0 }, { 0, 3 }, { 0, -3 }, { 2, 1 },.. 2024. 5. 16.
[백준] 11779: 최소비용 구하기 2 - JAVA https://www.acmicpc.net/problem/11779 풀이출발 도시부터 도착 도시까지 최소 비용으로 가야한다. 다익스트라 알고리즘을 사용하는 문제였다. 최소 비용, 경로에 포함된 도시의 개수, 방문한 도시를 출력해야 했다. 다익스트라 알고리즘으로 최소 비용을 구하고, int 배열로 비용을 저장하지 않고 class 배열을 만들어서 이전의 도시와 비용을 저장해줬다. 최소 비용을 구한 뒤 도착지부터 역추적하여 방문한 경로를 구했다. 역추적 하기 위해 class를 만들어 배열에 넣어준 것이다.  메모리: 54432KB시간: 576ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node imple.. 2024. 5. 13.

티스토리툴바