밤이 블로그

BOJ#2593 엘리베이터 * 문제https://www.acmicpc.net/problem/2593 * 풀이다익스트라를 이용해서 풀었습니다. 처음에 그래프 모델링에서 당황했는데 아래와 같이 해보았습니다.문제에 나와있는 예제에서 ArrayList elevator = new ArrayList();elevator : 각 엘리베이터에서 갈 수 있는 층 엘리베이터 1번 : [4, 7, 10]엘리베이터 2번 : [7, 12]엘리베이터 3번 : [4, 8, 12] ArrayList floor = new ArrayList();floor : 각 층에서 탈 수 있는 엘리베이터 4층 : [1, 3]7층 : [1, 2]8층 : [ 3 ]10층 : [ 1 ]12층 : [2, 3] 그리고 정점을 각 층이 아닌 엘리베이터로 정하였..

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#2665 미로 만들기 * 문제https://www.acmicpc.net/problem/2665Olympiad > 한국정보올림피아드 > KOI 1997 > 고등부 2번 * 풀이쉬운 문제입니다. 20년 묵은 문제네요, 😅 왜 쉽냐면,검은 방을 흰색 방으로 바꾸는 개수의 제한도 없고, 바꿀 때 필요한 규칙도 없기 때문입니다. 그냥 이 문제는.. 다익스트라 돌리면 됩니다. 비슷한 문제 : 1261번 - 알고스팟 https://www.acmicpc.net/problem/12612206번 - 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 * 나의 코드 https://github.com/stack07142/BOJ/blob/431a2fe10059904f604d38bc137..

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#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 <..

Dijkstra 다익스트라 알고리즘 (우선순위 큐를 사용하지 않는) http://stack07142.tistory.com/47 * 다익스트라 알고리즘 (Dijkstra algorithm) 1. 개요 : 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다. : 다익스트라 알고리즘은 각각의 꼭짓점 v에 대해 s(시작점)에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다. 알고리즘의 시작 시에 d[s]=0이고, s가 아닌 다른 모든 꼭짓점 v에 대해서는 d[v]=∞로 놓아 다른 꼭짓점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존..