매일 조금씩

문제 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이 다익스트라 알고리즘 문제이다. 특이점은 최소 비용 뿐만 아니라 최소 비용으로 가는 경로 또한 출력해야 한다는 점이다. cost 배열을 2차 배열로 만들어서 최소 비용과 함께 갱신할 때의 이전 노드값을 같이 저장하였다. 다익스트라 알고리즘 수행 후, 도착지 노드부터 이전 노드 값을 거꾸로 탐색하여 시작 노드까지의 경로를 구하였다. 소스코드 package d..

문제 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 다익스트라 알고리즘 사용 최소 벽 파괴 횟수를 갱신하면서 탐색 소스코드 package dijkstra; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class BOJ..

문제 https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 풀이 다익스트라 알고리즘을 사용하여 풀 수 있다. 보통 최소 거리(시간)을 저장할 배열로 1차 배열을 사용하지만 여기서는 비용을 고려해야 하므로 2차 배열로 생성 하여 사용한다. 소스코드 package dijkstra; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io..

문제 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이 문제가 바로 이해하기가 힘든데, 교차로는 노드이고 도로는 간선으로 생각하면 된다. 문제의 핵심은 시작지점에서 목적지까지 최단 거리로 가는데 g-h 간선을 통과했다는 점이다. 따라서, s -> 목적지 까지의 최단 거리 == s -> g까지의 최단 거리 + g-h 도로의 가중치 + g -> 목적지의 최단거리 s -> 목적지 까지의 최단 거리 == s -> h까지의 최단 거리 + h-g..

문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 간선 정보가 명시적으로 주어지며, 다익스트라 알고리즘으로 풀 수 있는 문제이다. 1. 다음 노드와 다음 노드로 이동 시의 가중치 값을 저장할 Edge 클래스를 구현한다. public static class Edge { int to; int weight; public Edge(int to, int weight){ this.to = to; this.weight..

문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이 오랜만에 다익스트라 알고리즘 문제를 풀어 보았다. 나는 아래와 같이 풀었다. 1. 간선에 대한 정보가 명시적으로 주어지지 않기 때문에 직접 만든다. 배열을 순회하면서 상하좌우를 체크하여 접근 가능한 좌표라면 현재 배열 좌표에 인접한 좌표라고 볼 수 있다. 이때 인접한 좌표의 배열 값이 해당 좌표를 가기 위한 가중치 값이 된다. for(int i = 0; i < N; i..

문제 https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 풀이 S지점에서 X라는 지점에 도착해서 X->A, X->B 로 갈라진다. 즉,..

#문제 https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr #풀이 다익스트라 알고리즘을 사용하면 풀 수 있다. #소스코드 import java.util.*; // 노드의 연결된 노드와 거리를 가짐 class Edge { int to; int distance; public Edge(int to, int distance){ this.to = to; this.distance = distance..