다익스트라 알고리즘14 [백준] 6087번 - 레이저 통신 [Java] https://www.acmicpc.net/problem/6087 1. 아이디어 각 위치에 대해 거울의 설치 횟수를 최소로 하며 도착할 수 있는지 판단하는 방식으로 다익스트라 알고리즘을 활용했다.2. 문제풀이 다익스트라 알고리즘에 활용할 노드 클래스는 위치와 방향, 거울 설치 횟수를 필드로 갖고 거울 설치 횟수에 대한 정렬 기준을 설정했다. 방문 체크와 거리 배열의 경우 위치 뿐만 아니라 방향에 대한 체크도 해줘야 했는데 같은 거울 설치 횟수로 도착해도 레이저의 방향이 다르면 이후 결과가 달라질 수 있기 때문이다. 시작 위치에서 모든 방향으로 레이저를 쏜 후 사방탐색을 하며 사방탐색 방향과 현재 레이저 방향이 일치하는지 90도 차이가 나는지에 따라 구분해서 구현하면 됐다. 다익스트라 종료 후 도착점에 .. 2025. 2. 10. [백준] 1162번 - 도로포장 [Java] https://www.acmicpc.net/problem/1162 1. 아이디어 다익스트라 알고리즘과 방문 체크 배열을 포장 횟수에 대해서도 체크하는 방식으로 해결할 수 있다.2. 문제풀이 다익스트라 알고리즘의 방문 체크 과정에서 각 도시를 몇 번 포장하고 방문했는지 체크하기 위해 2차원 배열을 활용했다. 거리 배열 역시 포장 횟수에 따라 기록하기 위해 2차원 배열로 설정했다. 이후 현재 도시와 연결된 다른 도시에 대해 포장을 하며 가는 경우와 포장을 하지 않고 가는 경우를 나눠서 다익스트라 알고리즘을 적용했다. 거리의 합이 int형을 넘어가게 돼서 거리 배열 초기화에 주의해야 했다. 추가로 정확히 K번 포장하는게 최단 거리가 아닐 수 있어서 거리 배열을 한번 순회하며 최단 거리를 찾아야 했다.3. 코.. 2025. 2. 2. [백준] 17835번 - 면접보는 승범이네 [Java] https://www.acmicpc.net/problem/17835 1. 아이디어 각 도시에서 면접장까지의 거리를 구하는 방식으로는 시간초과가 발생했다. 이를 해결하기 위해 면접장에서 도시까지의 거리를 구하는 방식으로 다익스트라 알고리즘을 활용했다.2. 문제풀이 면접장으로 주어진 모든 장소를 다익스트라 알고리즘의 출발점으로 설정했고 계산 후 거리 배열에서 가장 먼 도시의 번호와 거리를 구해서 반환하는 방식으로 구현했다. 거리 배열을 최댓값으로 초기화할 때 int형 최대 크기보다 크게 설정해야 함에 주의해야 한다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Node implements Compar.. 2025. 2. 2. [백준] 1238번 - 파티 [Java] https://www.acmicpc.net/problem/1238 1. 아이디어 다익스트라 알고리즘으로 해결할 수 있는데 다익스트라 알고리즘은 기본적으로 출발지에 대한 나머지 모든 지역까지의 최단 거리를 배열로 구할 수 있다. 이를 활용해서 간선의 방향을 바꾼 인접 리스트로 다익스트라 알고리즘을 적용하면 나머지 모든 지역에서 출발지까지의 최단 거리를 배열로 구할 수 있다.2. 문제풀이 입력 단계에서 정방향 인접 리스트와 역방향 인접리스트를 각각 생성했다. 이후 역방향 인접 리스트로 각 마을에서 X마을까지의 최단거리를 구하고 정방향 인접 리스트로 X마을에서 각 마을까지의 최단거리를 구했다. 이후 두 경로가 연결된 경로일 때 더한 값의 최댓값을 구하는 방식으로 구현했다.3. 코드 import java.io.. 2025. 2. 2. [백준] 14938번 - 서강그라운드 [Java] https://www.acmicpc.net/problem/14938 1. 아이디어 각 지역까지의 최단 거리를 통해 아이템의 합을 구하는 문제로 다익스트라 알고리즘을 활용할 수 있고 N이 최대 100이어서 플로이드 워셜 알고리즘으로도 해결할 수 있다.2. 문제풀이 다익스트라 알고리즘은 1번 지역부터 N번까지 각 지역을 출발지로 설정한 후 아이템의 합을 구해보며 최댓값을 찾는 방식으로 구현했고, 플로이드 워셜 알고리즘은 2차원 dp 테이블을 순회하며 각 행을 출발지로 생각하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main_Dijkstra { private static class Node implements Comparabl.. 2025. 2. 2. [백준] 4485번 - 녹색 옷 입은 애가 젤다지? [Java] https://www.acmicpc.net/problem/4485 1. 아이디어 동굴의 각 칸에서 루피를 최소한으로 잃으면서 도착점으로 가야하는 문제로 사방탐색 + 다익스트라 알고리즘을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 다익스트라 알고리즘에서 거리 배열의 갱신에 동굴 정보를 적용하는 부분만 신경쓰면 무난히 해결할 수 있었다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Node implements Comparable { int r; int c; int sum; public Node(int r, int c, int sum) { .. 2025. 2. 1. [백준] 11779번 - 최소비용 구하기 2 [Java] https://www.acmicpc.net/problem/11779 1. 아이디어 이전 최소비용 구하기 문제에서 최소비용으로 가는 경로까지 출력하는 문제로 이전에 방문한 정점을 기록하는 before 배열을 활용해서 해결할 수 있었다.([코딩테스트 준비/백준] - [백준] 1916번 - 최소비용 구하기 [Java])2. 문제풀이 다익스트라 알고리즘에서 최소 비용 경로가 갱신되는 순간 before 배열에서 이전에 방문했던 정점을 기록하면 이후 역순으로 조회해서 경로를 찾아갈 수 있다. 경로가 도착점부터 시작점까지 역순으로 구해지므로 이를 Stack에 담은 후 Stringbuilder와 조합해서 출력하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public.. 2025. 2. 1. [백준] 1916번 - 최소비용 구하기 [Java] https://www.acmicpc.net/problem/1916 1. 아이디어 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 구하는 문제로 다익스트라 알고리즘을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 다익스트라 알고리즘 구현만 할 수 있으면 간단하게 해결할 수 있었다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Node implements Comparable { int v; int w; public Node(int v, int w) { this.v = v; this.w = w; } .. 2025. 2. 1. [백준] 1504번 - 특정한 최단 경로 [Java] https://www.acmicpc.net/problem/1504 1. 아이디어 시작점에서 두 점 v1, v2를 경유해서 끝점으로 가는 최단 거리를 구하는 문제로 1 -> v1 -> v2 -> N 또는 1 -> v2 -> v1 -> N 두 가지 경로에 대한 다익스트라 알고리즘으로 해결할 수 있다.2. 문제풀이 다익스트라 알고리즘으로 각 경로마다 거리를 구하면 해결할 수 있는데 이때 연결되지 않은 두 점이어서 경로가 존재하지 않을 경우 -1을 반환했고 이를 통해 경로가 존재하는지 여부를 파악해서 경우에 맞게 출력하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Node imple.. 2025. 2. 1. [백준] 1753번 - 최단경로 [Java] https://www.acmicpc.net/problem/1753 1. 아이디어 다익스트라 알고리즘으로 간단하게 해결할 수 있다.2. 문제풀이 K를 시작점으로 하는 다익스트라 알고리즘을 구현하면 거리 배열이 K를 시작점으로 다른 모든 정점으로 가는 최단 거리가 저장되게 돼서 그냥 거리 배열을 반환하면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Node implements Comparable { int v; int w; public Node(int v, int w) { this.v = v; this.w = w; .. 2025. 2. 1. [백준] 14497번 - 주난의 난(難) [Java] https://www.acmicpc.net/problem/14497 1. 아이디어 다익스트라 알고리즘 또는 0-1 BFS 알고리즘으로 해결할 수 있다.2. 문제풀이 (x1, y1)에서 (x2, y2)까지 최소한의 점프 횟수로 도달해야하는 문제로 점프 한번에 한 겹의 친구 벽을 없앨 수 있으므로 이를 가중치가 1인 간선으로 이동이라고 생각하면 최단 경로를 구하는 다익스트라 알고리즘으로 풀이할 수 있다. 빈공간은 가중치가 0인 간선으로 생각하면 가중치가 0, 1 두가지로 이루어진 상황이므로 0-1 BFS 알고리즘으로도 해결할 수 있다. 두 가지 모두 간단한 구현만 하면 해결할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main_BFS01 { .. 2025. 2. 1. [백준] 2665번 - 미로만들기 [Java] https://www.acmicpc.net/problem/2665 1. 아이디어 다익스트라 알고리즘 또는 0-1 BFS 알고리즘으로 해결할 수 있다.2. 문제풀이 (1, 1)에서 (N, N)까지 벽을 최소한으로 바꾸면서 이동해야 하는 문제로 벽이 있는 칸을 가중치 1인 간선으로 이동, 벽이 없는 칸은 가중치 0인 간선으로 이동이라고 했을 때 0과 1의 가중치를 갖는 간선으로 이루어진 그래프에서 최단 경로로 이동하는 문제가 된다. 이는 다익스트라 알고리즘으로 해결할 수 있고 가중치가 0과 1 두가지만 있는 경우 Deque 자료구조를 활용한 0-1 BFS 알고리즘으로도 해결할 수 있다. 두 가지 모두 간단하게 구현만하면 해결할 수 있다.3. 코드 import java.io.*;import java.util.. 2025. 2. 1. 이전 1 2 다음
