막내의 막무가내 프로그래밍 & 일상

www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 백준 다익스트라 유형의 10282번 해킹 문제를 풀어봤습니다. ㅎㅎ 다익스트라의 기본 유형 문제였습니다. 풀이는 다음과 같습니다. [Java] import java.util.*; public class Main { private static int T; //테스트 케이스 수 private static int N; //컴퓨터 개수 private static int D; //의존성 개수 private static in..

www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 백준 다익스트라 유형을 풀어봤습니다. ㅎㅎ 어렸을때 닌텐도로 젤다의 전설 게임을 한 경험이 있는데 문제를 읽으며 젤다가 그 주인공이 아니라 공주였다는 사실을 저도 처음알았네요 ;; 문제에 대해 간략히 쉽게 설명하면 N*N 맵이 있고 (0,0) 에서 (N,N) 까지 가는 최소비용을 구하는 문제였습니다. 이전에 ArrayList 배열 즉 인접리스트를 사용하여 풀었던 다익스트라 문제와 다르게 BFS..

www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 백준 다익스트라 유형의 특정 거리의 도시 찾기 문제를 풀어봤습니다. ㅎㅎ 특정 경로에서의 최단경로 즉 1:N의 최단 경로를 구하면 되는 문제이므로 다익스트라 알고리즘을 사용하면 됩니다. (정점 개수가 V, 간선 개수가 E일 때 시간복잡도는 O(ElogV)입니다.) 풀이는 다음과 같습니다. [Java] import java.util.Arra..

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 프로그래머스 LV2 배달 문제를 풀어봤습니다. ㅎㅎ 1번 마을에서 K 이하의 시간으로 배달을 갈 수 있는 마을의 개수를 구하는 문제입니다. 그래서 1번 마을에서 각 마을간의 최단경로(최단시간)를 구해서 K시간 이하가 몇개 있는지 답을 구하면 됩니다. 다익스트라가 사용되며 도시의 개수는 N개 그리고 한 도시의 주변 개수는 road.length 이므로 각..

www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 백준 다익스트라 분류 문제에 있는 최소비용 구하기 2 입니다. 지나간 도시의 개수와 경로도 출력해야하는 특징이 있는 문제였습니다. 나머지는 원래 다익스트라 풀던대로 풀이했습니다. P.S 그리고 미리 말하면 예제에서는 출력이 1 3 5 가 나오는데 제 갈 수 있는 최단경로가 여러개가 생길 수 있기 떄문에 1 4 5 도 맞습니다. //역추적 Stack stack = new Stack..

www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 백준 최단경로 단계별풀기 두 번째 문제를 풀어봤습니다. 시작점에서 도착점까지의 최단 경로를 구해야하는데 반드시 거쳐야 할 정점 두 개를 조건으로 추가되었습니다. 반드시 지나야하는 정점이 v1, v2 인데 start -> v1 -> v2 -> end start -> v2 -> v1 -> end 두 가지 로직이 가능합니다. 이를 적용한 풀이입니다. [Java] impor..

www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 백준 최단경로 단계별풀기의 첫번째 문제입니다. 최단경로의 가장 베이스적인 문제입니다. 풀이는 주석에 적어놓았습니다. 또 설명은 다음 블로그에서 그림과 함께 잘 해놓으셨습니다. ㅎㅎ dragon-h.tistory.com/20 [백준 1753 : JAVA] 최단경로 / 다익스트라 개요 이 문제는 가중치가 1이 아니고 음의 가중치도 아니기 때문에 다익스트라를 이용하여 풀이할 수 있다. 다익..