최단 경로14 [백준] 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. [백준] 21278: 호석이 두 마리 치킨 - JAVA https://www.acmicpc.net/problem/21278 풀이건물들이 도로로 연결되어있고, 2개의 건물을 골라 치킨집을 열어야 한다. 이때, 치킨집으로부터 각 건물들까지의 거리의 합이 최소가 되게 해야한다. 먼저 플로이드-워셜 알고리즘을 통해 각 건물들 사이의 거리를 구했다. for (int k = 1; k 건물들 사이의 거리를 구한 후, 2개의 건물을 정해 거리의 합을 계산해 정답을 갱신해주었다. 메모리: 17220KB시간: 192ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int n, m; static int[][] dist; public static void main(String[.. 2024. 7. 13. [백준] 2458: 키 순서 - JAVA https://www.acmicpc.net/problem/2458 풀이1 ~ n번 학생들에 대해 m개의 관계가 주어지는데, 각각의 관계에는 a번 학생이 b번 학생보다 작다는 것을 알려준다. 이 관계들을 이용해 자신이 몇 번째 등수인지 정확히 알 수 있는 사람의 수를 세는 문제이다. 모든 정점끼리 탐색을 해야하기 때문에 플로이드-워셜 알고리즘을 사용했다. 플로이드-워셜은 O(n^3)의 시간복잡도를 갖는다. 핵심 로직은 다음과 같다.for (int k = 0; k i와 k가 연결되어있고, k와 j가 연결되어 있다면, i와 j는 연결되었다고 보는 것이다. 모든 정점끼리 연결 여부를 체크했다면 각 학생별로 연결된 학생의 수가 n-1인지 확인하면 된다. 메모리: 36932KB시간: 604ms언어: Java 11.. 2024. 5. 19. [백준] 11657: 타임머신 - JAVA https://www.acmicpc.net/problem/11657 풀이도시마다 연결된 줄이 있고, 줄마다 가중치가 있다. 가중치에는 음수값도 있어서 1번도시에서 어떤 도시로 가는 과정에서 무한히 오래 전으로 돌릴 수 있으면 -1을 출력해야한다. 그렇지 않다면 2번~n번 도시까지 가는 가장 빠른 시간을 출력한다. 음수 가중치가 있기 때문에 벨만포드 알고리즘을 사용하는 문제였다. 벨만포드 알고리즘에서는 우선 `정점의 개수 - 1`만큼 루프를 돈다. 먼저 정점의 사이즈만큼 dist 배열을 만들어 출발지를 0으로 설정하고 나머지 값은 INF로 설정한다. `정점의 개수 - 1`만큼 루프를 돌면서 dist의 값이 INF가 아닌 정점에 대해 연결 된 정점까지 걸리는 cost를 최솟값으로 갱신한다. `정점의 개수 -.. 2024. 5. 19. [백준] 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. [백준] 1956: 운동 - JAVA https://www.acmicpc.net/problem/1956 풀이v개의 정점과 e개의 간선이 주어진다. 출발점에서 다시 출발점으로 돌아오는 사이클이 있는지, 있다면 최솟값을 구하는 문제이다. 모든 정점에서 다른 모든 정점까지의 최단경로가 필요하다. -> 플로이드 워셜 알고리즘을 사용한다. 원래 알고있던 플로이드 워셜에서는 거리를 저장할 이차원배열을 만들고, 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화를 했었다. 하지만 이 문제에서는 자기 자신에서 자기 자신으로 돌아와야하므로 다른 값들과 마찬가지로 INF로 초기화하였다. 그리고나서 플로이드 워셜 알고리즘을 통해 i정점에서 k를 거쳐 j로 이동하는 최솟값을 갱신해주면 자기 자신으로 다시 돌아오는 거리도 갱신된다. `dist[i][i]` 중 .. 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. 이전 1 2 다음