기록방

👉 문제링크🔸 문제 분석 🔸1번 도시부터 다른 도시로 가는 K번째 최단 거리를 구해야 한다.K번째 최단 경로가 없으면 -1 출력한다.🔸 문제 풀이 🔸한 노드부터 다른 노드까지의 최단 거리를 구하므로, 다익스트라 (Dijkstra) 알고리즘을 선택한다.일반적인 다익스트라와 다르게, 거리를 업데이트이트 하지 않고 우선 순위 큐에 다시 넣는다.무한 순환 혹은 너무 많은 원소가 생기지 않도록, K개 까지만 거리를 구한다.🔸 코드 🔸import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWrite..

👉 문제링크 🔸 문제 분석 🔸N개의 도시 사이 M개의 도로가 주어진다. 각 도로를 건너는 시간이 있고, 출발지와 도착지가 주어진다.도로는 출발지부터 도착지까지 단방향 비순환 그래프이다.많은 경로 중에 가장 늦게 도착하는 경로에서 지나는 도로의 수 총합을 출력한다.🔸 문제 풀이 🔸출발지부터 도착지까지 단방향 비순환 그래프이므로, 위상 정렬(Topology Sort)을 통해 최대값을 구할 수 있다.건너온 경로의 수를 카운트 해야하므로 역방향 탐색이 필요하다.1분도 쉬지 않고 달린 경로이므로 현재 시간과 도로의 소요 시간의 차이가 맞아 떨어져야 한다.경로를 중복되게 체크하지 않기 위해서 도시를 방문처리 한다.🔸 코드 🔸import java.io.*;import java.util.ArrayDeque..

👉 문제링크🔸 문제 분석 🔸스타크레프트 같은 게임에서 각 건물을 짓는데 필요한 최소 시간을 구해보자.N개의 건물 별 짓는 시간과 먼저 지어져야 하는 건물의 번호가 주어진다.🔸 문제 풀이 🔸선행 되어야 하는 번호가 주어지므로 위상 정렬(Topology Sort)을 활용해 풀이할 수 있다.선행 건물 건설 직후 해당 건물을 짓는데, 선행 건물이 여러개일 경우 순서를 정할 수 없다.따라서 선행 건물이 지어지는 시간의 최대값 + 현재 건물을 짓는 시간을 구한다.🔸 코드 🔸import java.io.*;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Queue;import java.util.StringTokenizer;pu..

👉 문제링크🔸 문제 분석 🔸N x M 직사각형 땅에 수영장을 만든다. 격자 속 숫자가 해당 땅의 높이이다.물을 채워야 하는데, 물은 상하좌우 높은 곳에서 낮은 곳으로만 흐르고 격자 밖으로는 무한정 흘러나가 버린다.채울 수 있는 물의 양의 최대값을 출력한다.🔸 문제 풀이 🔸상하좌우 인접 땅으로 흐르는 물의 이동을 구현하기 위해서 BFS를 사용한다.외각에 붙은 땅은 물이 고일 수 없으므로, 역방향 BFS를 통해 이어진 땅들을 모두 체크한다.물이 고일 수 있는 땅들에 물을 채우고 총합을 출력한다.물 높이의 최대값은 2가지 기준을 유의해서 정한다.해당 높이보다 높아지면 물이 흘러나가버리는 경우 : 최대값의 인덱스가 체크된 경우흘러나가지는 않지만, 땅이 높아서 조금 더 높이 물이 고이는 경우 : 최대값의..

👉 문제링크🔸 문제 분석 🔸N개의 지역과 M개의 횡단보도가 있다.횡단보도는 입력 순서대로 0~M-1 초에 파란불이 켜져 건널 수 있다.1번 지역부터 출발해 N번 지역에 도착할 수 있는 최단 시간을 출력한다.🔸 문제 풀이 🔸N이 최대 10만, M이 최대 70만이므로 BFS로 최단시간을 구하면 시간초과가 난다. 따라서 Dijkstra(다익스트라) 알고리즘을 이용해 최단시간을 구한다.현재 지역에서 갈 수 있는 다음 지역을 건널 때 걸리는 시간을 계산하고, 기록 된 소요 시간보다 작다면 업데이트한다.🔸 코드 🔸import java.io.*;import java.util.ArrayList;import java.util.PriorityQueue;import java.util.Queue;import ja..