밤이 블로그

BOJ#1219 오민식의 고민 * 문제https://www.acmicpc.net/problem/1219 * 풀이벨만-포드 최단거리 문제입니다. 간선 cost는 음수이고, 각 노드마다 추가로 돈을 벌 수 있습니다.원하는 것은 S(시작점)에서 D(도착점)까지 갈 때 최대로 벌 수 있는 돈의 액수를 구하는 것입니다. 일반적으로 문제에서 간선의 cost가 양수로 주어지는 반면,이 문제에서는 간선 cost가 음수이므로음수 사이클은 문제가 되지 않고 반대로 양수 사이클인 경우가 문제 됩니다. 벨만-포드 알고리즘에 따라 (엣지수(M)만큼 Relaxation)을 N-1번 반복하고N번째에도 Relaxation이 되면 사이클이 존재함을 알 수 있습니다. 그러나 우리는 사이클 유무를 판단하는 것이 목적이 아니라시작점에서 도..

BOJ#4485 녹색 옷 입은 애가 젤다지? * 문제https://www.acmicpc.net/problem/4485 * 풀이다익스트라 (Priority Queue 이용)개념만 알면 풀 수 있는 기본 문제이므로 설명은 생략합니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/7abd485c7bdc3853570ff8d262afbd03b7234709/BOJ%234485/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenize..

BOJ#13911 집 구하기 * 문제https://www.acmicpc.net/problem/13911 University > 서강대학교 > 제 12회 총장배 서강대학교 프로그래밍 대회 Master F번 * 풀이매우 매우 추천하는 문제입니다. - 처음 생각한 알고리즘 1. 맥도날드 지점별로 다익스트라2. 스타벅스 지점별로 다익스트라3. 조건 만족하는 것 찾아내기 문제를 본격적으로 풀어보려는데,, 뭔가 찜찜합니다.입력값 범위가 심상치 않아 문제를 풀기전에 시간복잡도를 계산해봅니다. V ≤ 10,000, E ≤ 300,000 맥도날드 다익스트라 (V-2)번 : O(E*log(V)) * V-2번스타벅스 다익스트라 (V-2)번 : O(E*log(V)) * V-2번조건 만족하는 것 찾아내기 : ?? 결론 : 시간..

BOJ#12930 두 가중치 * 문제https://www.acmicpc.net/problem/12930 * 풀이최단거리 다익스트라 알고리즘으로 풀어봅시다.개념만 충실히 알고 계시다면 어렵지 않게 풀수 있을듯 합니다. 따라서 풀이 설명은 생략합니다. * 나의 코드https://github.com/stack07142/BOJ/blob/71d4c79293704f4539e025b72a7470964685156c/BOJ%2312930_Weights/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Pri..

BOJ#1854 K번째 최단경로 찾기 * 문제https://www.acmicpc.net/problem/1854 * 풀이아이디어 자체는 간단합니다.다익스트라 알고리즘에서 버려지는 거리값들을 버리지 않고 K개 모아두면 됩니다.(최단 거리 값이 아니여서 Relaxation에 쓰이지 않는 값들, 혹은 최단 거리 값으로 교체되어지는 값들) http://docs.oracle.com/javase/8/docs/api/ PriorityQueuepublic PriorityQueue(int initialCapacity, Comparator

BOJ#1504 특정한 최단 경로 * 문제https://www.acmicpc.net/problem/1504 * 풀이중간에 꼭 거쳐야하는 노드는 2개이므로, 각각을 node1, node2라고 해봅시다. 최단경로는 아래 두개의 경로 중 하나가 될 것입니다. 1 → .. → node1 → .. → node2 → .. → N1 → .. → node2 → .. → node1 → .. → N 따라서 1, node1, node2를 각각 출발점으로 하는 다익스트라를 3번 돌리면 답을 찾을 수 있습니다.(다익스트라 알고리즘 개념에 따라 중간에 어떤 노드들을 거치는지는 관심을 안써도 됩니다.) * 나의 코드https://github.com/stack07142/BOJ/blob/7c385f97d7761734c15c7c1fe4..

BOJ#5214 환승 * 문제https://www.acmicpc.net/problem/5214 * 풀이 하이퍼튜브는 M개만큼 있고, 각각의 하이퍼튜브는 K개의 노드를 연결하고 있다. -> 간선 정보가 여태까지 풀어본 문제와는 다르게 주어짐-> 간선 정보를 어떤 자료구조에 어떻게 담을지 고민-> 인접 행렬은 메모리 초과 (N 각 하이퍼튜브는 최대 1000개의 노드 정보를 담고 있으므로, 이것을 일일이 짝을 맞추어가며 간선 정보를 저장하기 쉽지 않다. 생각한 아이디어는 다음과 같다.각 하이퍼튜브에 연결된 노드 정보는 아래와 같고1 2 3 1 4 5 3 6 7 5 6 7 6 8 9 각 하이퍼튜브에 속하는 노드에 임의의 더미 노드를 생성하여 연결시킨다.10 ↔ 1, 10 ↔ 2, 10 ↔ 311 ↔ 1, 11 ..

BOJ#1261 알고스팟 * 문제https://www.acmicpc.net/problem/1261 * 풀이 다익스트라 알고리즘 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%231261_Algospot/src/Main.java import java.io.IOException; import java.io.InputStreamReader; import java.util.*; import java.io.BufferedReader; /** * BOJ#1261 알고스팟 * https://www.acmicpc.net/problem/1261 */ public class Main { static int[][] map = new int[101][101]; stat..

BOJ#1162 도로포장 * 문제https://www.acmicpc.net/problem/1162 * 풀이그래프 최단거리를 찾는 문제로써, 다익스트라 알고리즘으로 문제를 풀 수 있습니다.그러나 K개 이하로 도로 포장하여 가중치를 제거할 수 있기 때문에 추가적인 문제 풀이 방법이 요구됩니다. 따라서 기존의 dist 배열을 아래와 같이 바꿔봅시다.-기존의 dist[i] : 시작점에서 i까지의 최단 경로 cost라고 한다면-이 문제에서 dist[i][k] : 시작점에서 i까지 k개 도로를 포장하여 가는 최단 경로 cost 기존과 동일하게 dijkstra 알고리즘을 쓰되 각 경로에서 포장하는 경우, 포장하지 않는 경우를 구분하여 진행하면 되겠습니다. * 나의 코드https://github.com/stack071..

BOJ#1753 최단경로 * 문제https://www.acmicpc.net/problem/1753 * 풀이 다익스트라 최단 경로 문제입니다.주의할 점으로는 V와 E의 범위입니다. (1 dist[here] + W[here][i]) { dist[i] = dist[here] + W[here][i]; pq.add(new Element(i, dist[i])); } } } } } } class Element implements Comparable { int node; int dist; Element(int node, int dist) { this.node = node; this.dist = dist; } @Override public int compareTo(Element o) { return this.dist <..