매일 조금씩

문제 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..