문제 - 천개의 정거장(다익스트라에서 간선 생성) (다시 풀기)
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-thousand-stops/description
천 개의 정거장 설명 | 코드트리
천 개의 정거장의 요구사항을 정확히 분석하고, 적절한 알고리즘을 고안해 두 번째 단계 중급 문제를 해결해보세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int A,B,N;
static ArrayList<Integer>[] bus;
// bus i cost list
static int[] cli;
static ArrayList<int[]>[] g;
static final long INF = 1_000_000_000L * 1_000 + 1;
// 일단 최소비용 배열 B->A 방향으로 구하고
// 그걸로 최소비용 DAG 만들어서 거기서 B->A 최소시간 구하기
// -> 그냥 pq 기준 2개 넣어서 구하기
static long[] dijkstra(){
long[] cost = new long[1001];
long[] time = new long[1001];
Arrays.fill(time, INF);
Arrays.fill(cost, INF);
cost[A] = 0;
time[A] = 0;
PriorityQueue<long[]> q = new PriorityQueue<>((a,b)->{
if(a[1] != b[1])
return Long.compare(a[1], b[1]);
return Long.compare(a[2], b[2]);
});
// next, cost, time
q.add(new long[]{A,0,0});
while(!q.isEmpty()){
long[] cur = q.poll();
int ci = (int) cur[0];
long cc = cur[1];
long ct = cur[2];
if(cost[ci] != cc)
continue;
if(time[ci] != ct)
continue;
for(int[] n : g[ci]){
int bi = n[0];
int bpos = n[1];
for(int np = bpos+1; np < bus[bi].size(); np++){
int ni = bus[bi].get(np);
long nc = cli[bi];
int nt = np-bpos;
if(cost[ni] > cost[ci] + nc){
cost[ni] = cost[ci] + nc;
time[ni] = time[ci] + nt;
q.add(new long[]{(long) ni, cost[ni], time[ni]});
}
else if(cost[ni] == cost[ci] + nc && time[ni] > time[ci] + nt){
time[ni] = time[ci] + nt;
q.add(new long[]{(long) ni, cost[ni], time[ni]});
}
}
}
}
if(cost[B] == INF)
return new long[]{-1,-1};
return new long[]{cost[B], time[B]};
}
public static void main(String[] args) throws IOException{
A = read();
B = read();
N = read();
cli = new int[N];
bus = new ArrayList[N];
for(int i = 0; i<N; i++)
bus[i] = new ArrayList<>();
for(int i = 0; i<N; i++){
cli[i] = read();
int cnt = read();
for(int j = 0; j<cnt; j++){
int cur = read();
bus[i].add(cur);
}
}
g = new ArrayList[1001];
for(int i = 1; i<= 1000; i++){
g[i] = new ArrayList<>();
}
for(int n = 0; n<N; n++){
for(int i = 0; i<bus[n].size(); i++){
g[bus[n].get(i)].add(new int[]{n, i});
}
}
long[] ans = dijkstra();
System.out.print(ans[0]+" "+ans[1]);
}
}문제 원문
개의 지점에 각각 부터 까지의 숫자가 매겨져 있습니다. 개의 버스가 이 지점들 사이를 정해진 노선대로 돌아다니며, 각 버스는 다음과 같은 특징이 있습니다.
- 각 노선은 최소 개 이상의 지점을 포함하고 있으며, 한 노선 내에 같은 지점이 두 번 이상 나올 수는 없습니다.
- 버스는 노선을 순서대로 운행하며, 마지막 지점에 도착하면 다시 처음부터 순서대로 운행을 시작합니다.
- 각 버스에는 탑승료가 있으며, 특정 버스에서 내렸다가 다른 버스로 갈아탈 때에는 탑승료를 다시 지불해야 합니다.
- 각 버스의 일부 노선만 이용하는 것도 가능하며, 이 경우에도 탑승료는 동일하게 지불해야 합니다.
- 버스가 마지막 지점에 도착하면 반드시 내려야 하며, 버스로 연속된 두 지점 사이를 이동하는데에는 초가 걸립니다.
주어진 버스들을 활용해 번 지점부터 번 지점까지 이동할 때 필요한 최소 비용과 이러한 최소 비용을 만족시키기 위해 걸리는 버스 탑승 시간 중 최솟값을 구하는 프로그램을 작성해보세요.
사고의 흐름 및 풀이
처음에는 그냥 다익스트라 2개의 기준으로 돌려서 풀면 될거라고 생각했는데 그래프가 생성할 수 있는 간선이 너무 많아서 터져버림. 다익스트라 자체는 cost 먼저 그다음 time 오름차순으로 우선순위 주고 각각 배열 따로따로 두고 relaxing 하면 됨.
인접 그래프로 일반적으로 생성하면 버스 노선 길이(m) 마다 O(m^2) 간선이 발생해서 터짐.
다익스트라에서 relaxing 할 때 간선을 생성하는 on the fly 기법을 사용해야 안 터짐.
상태 = 현재 지점
간선 = 이 지점에서 탈 수 있는 버스를 타고 뒤쪽 정점으로 이동
bus 배열에는 해당 노선을 이루는 정점들을 저장하고 cli 배열에는 각 노선의 비용을 저장함
그리고 ArrayList<int[]>형 배열 g에서는 역그래프로 생성함
for(int n = 0; n<N; n++){
for(int i = 0; i<bus[n].size(); i++){
g[bus[n].get(i)].add(new int[]{n, i});
}
}-> g[v] 에 지점 v에서 탈 수 있는 버스와 위치를 저장함.
그리고 다익스트라에서 현재 정점 ci에서 탈수 있는 노선(bi)과 버스의 현재 위치(bpos)를 알면
갈 수 있는 다음 위치는 [bpos+1, bus[bi].size()-1] 이고 이용 비용은 cli[ bi ] 이며
이동 시간은 각 지점 하나 사이를 이동할 때마다 1초가 걸리므로 nextpos - bpos 이다.
-> 각자 ni, nc, nt로 놓고 cost[ni] > cost[ci] + nc 일때 비용과 시간을 모두 갱신하고
cost[ni] == cost [ci] + nc 이고 time[ni] > time[ci] + nt 일때는 시간만 갱신해서 relaxation 하고
queue에 다음 상태를 넣어주면 된다.
또한 INF의 경우 비용의 경우 N이 최대 1000이고 탑승료가 10^9이므로 둘을 곱하고 +1해주면 되고
time INF의 경우 노선을 이루는 점의 갯수가 최대 100이고 N이 최대 1000이므로 10만? 해주면 되는데
그냥 위에껄로 long으로 잡고 계산함
문제 - 여러 정점에서 가장 가까운 거리의 최댓값 (다중 시작 다익스트라)
가장 가까운 거리의 최댓값 설명 | 코드트리
가장 가까운 거리의 최댓값의 요구사항을 정확히 분석하고, 적절한 알고리즘을 고안해 두 번째 단계 중급 문제를 해결해보세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N,M,A,B,C;
static ArrayList<int[]>[] g;
static ArrayList<Integer> sl = new ArrayList<>();
static final long INF = 10000 * 100_000L + 1;
static long dijkstra(){
PriorityQueue<long[]> q = new PriorityQueue<>(Comparator.comparingLong(a->a[1]));
long[] dist = new long[N+1];
Arrays.fill(dist, INF);
for(int si : sl){
dist[si] = 0;
q.add(new long[]{si, 0});
}
while(!q.isEmpty()){
long[] cur = q.poll();
int ci =(int) cur[0];
long cd = cur[1];
if(dist[ci] != cd)
continue;
for(int[] n : g[ci]){
int ni = n[0];
int nl = n[1];
if(dist[ni] > dist[ci] + nl){
dist[ni] = dist[ci] + nl;
q.add(new long[]{(long)ni, dist[ni]});
}
}
}
long ans = 0;
for(int i = 1; i<=N; i++){
ans = Math.max(ans, dist[i]);
}
return ans;
}
public static void main(String[] args) throws IOException{
N = read();
M = read();
for(int i = 0; i<3; i++){
sl.add(read());
}
g = new ArrayList[N+1];
for(int i = 1; i<=N; i++)
g[i] = new ArrayList<>();
while(M-->0){
int u = read();
int v = read();
int w = read();
g[u].add(new int[]{v,w});
g[v].add(new int[]{u,w});
}
System.out.print(dijkstra());
}
}풀이 요약
시작 정점 여러개에 대한 최단거리 중에 가장 먼 것을 찾는 것이므로
다중 시작 다익스트라에 최초 큐 상태에 A,B,C를 넣고 시작함
그리고 만들어진 long형 dist 배열에서 그중 먼 것이니까 최댓값을 갱신해서 출력함
-> 가중치가 모두 같다면 다중 시작 BFS이고 다르다면 다중 시작 다익스트라임.
문제 - 다른 경로로 이동 (최단 경로 판별)
다른 경로로 이동 설명 | 코드트리
다른 경로로 이동의 요구사항을 정확히 분석하고, 적절한 알고리즘을 고안해 두 번째 단계 중급 문제를 해결해보세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N,M;
static int[][] cost;
static ArrayList<int[]>[] g;
static Map<Long, Integer> map = new HashMap<>();
static final long INF = 100_000 * 100_000L + 1;
static long itol(int i, int j){
return (((long)i)<<32) + j;
}
static long[] dijkstra(int s, boolean isSecond){
long[] dist = new long[N+1];
Arrays.fill(dist, INF);
dist[s] = 0;
PriorityQueue<long[]> q = new PriorityQueue<>(Comparator.comparingLong(a->a[1]));
q.add(new long[]{s, 0});
while(!q.isEmpty()){
long[] cur = q.poll();
int ci = (int) cur[0];
long cd = cur[1];
if(dist[ci] != cd)
continue;
for(int[] n : g[ci]){
int ni = n[0];
int nd = n[1];
if(isSecond && map.containsKey(itol(ci, ni)))
continue;
if(dist[ni] > dist[ci] + nd){
dist[ni] = dist[ci] + nd;
q.add(new long[]{ni, dist[ni]});
}
}
}
return dist;
}
public static void main(String[] args) throws IOException{
N = read();
M = read();
cost = new int[N+1][N+1];
while(M-->0){
int u = read();
int v = read();
int w = read();
if(cost[u][v] != 0)
cost[u][v] = cost[v][u] = Math.min(cost[u][v], w);
else
cost[u][v] = cost[v][u] = w;
}
g = new ArrayList[N+1];
for(int i = 1; i<=N; i++)
g[i] = new ArrayList<>();
for(int i = 1; i<=N; i++){
for(int j = 1; j<=N; j++){
if(cost[i][j] == 0)
continue;
g[i].add(new int[]{j,cost[i][j]});
}
}
long[] distSE = dijkstra(1,false);
long[] distES = dijkstra(N,false);
if(distSE[N] == INF){
System.out.print(-1);
return;
}
int cur = 1;
while(cur != N){
for(int[] n : g[cur]){
int ni = n[0];
int nd = n[1];
if(distSE[cur] + nd + distES[ni] == distSE[N]){
map.put(itol(cur, ni), nd);
map.put(itol(ni, cur), nd);
cur = ni;
break;
}
}
}
long[] dist2 = dijkstra(1, true);
System.out.print(dist2[N]);
}
}사고의 흐름
A가 사전순 최단경로를 사용해서 1->N으로 이동했을 때 B는 A가 사용하지 않은 길만 따라 최단경로로 1->N 이동했을때 거리 값
이는 최초의 사전순 최단경로를 찾아내서 필터링하고 다시 B가 1->N으로 다익스트라를 하면 된다.
풀이
먼저 중복 간선이 들어올 수 있다고 했으니 cost 배열로 최솟값만 남겨놓고 ArrayList 배열 형태의 그래프를 만든다.
-> cost 배열 자체가 i, j를 [1,N] 으로 순회해서 그래프를 생성하기 때문에 따로 사전순 조건을 위해 정렬할 필요가 없다.
원래 역그래프로 한번 다익스트라를 돌려서 E->S 방향의 dist를 구해놓고
그 dist를 보면서 그리디하게 최단 경로상의 사전순 최초 다음 정점을 하나 고르고 break 하는 방식의 경로 복원은 하려했는데
좀 꼬여서 다익스트라를 2번하고 distSE[cur] + nd + distES[ni] = distSE[N] 같은 강한 조건으로 필터링했다.
근데 다시 생각해보니까 2번 할 필요가 없고 역방향으로 한번만 해주면 될 거 같았다.
distES[N] = 0으로 시작하는 역방향 다익스트라 한번하고 1->N 방향으로 경로복원을 해 준다.
복원 조건은 cur -> N의 최단거리가 cur -> ni -> N 으로 분해될 수 있으므로
distES[ni] + nd == distES[cur] 가 성립할때 최단경로에 포함된 간선이다.
간선 자체는 long 형으로 i,j 를 key로 삼아서 map에 저장해주고 B는 그 간선들을 피해서 1->N 방향으로 다익스트라 돌림.
만약 모든 최단경로 경우의 수가 필요해서 DAG를 만든다면
경로 복원에서 break 안하고 그냥 모든 조건을 만족하는 간선들을 최단경로 DAG 그래프 자체에 추가하면 된다.
문제 - 가장 긴 왕복 거리(역그래프의 최단거리 동치)
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-longest-round-trip/description
가장 긴 왕복 거리 설명 | 코드트리
가장 긴 왕복 거리의 요구사항을 정확히 분석하고, 적절한 알고리즘을 고안해 두 번째 단계 중급 문제를 해결해보세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N, M, X;
static ArrayList<int[]>[] g;
static ArrayList<int[]>[] rg;
static final long INF = 10_000 * 100_000 + 1;
static long[] dijkstra(ArrayList<int[]>[] gg){
long[] dist =new long[N+1];
Arrays.fill(dist, INF);
dist[X] = 0;
PriorityQueue<long[]> q = new PriorityQueue<>(Comparator.comparingLong(a->a[1]));
q.add(new long[]{X, 0});
while(!q.isEmpty()){
long[] cur = q.poll();
int ci = (int) cur[0];
long cd = cur[1];
if(dist[ci] != cd)
continue;
for(int[] n : gg[ci]){
int ni = n[0];
int nd = n[1];
if(dist[ni] > dist[ci] + nd){
dist[ni] = dist[ci] + nd;
q.add(new long[]{(long) ni, dist[ni]});
}
}
}
return dist;
}
public static void main(String[] args) throws IOException{
N = read();
M = read();
X = read();
g = new ArrayList[N+1];
rg = new ArrayList[N+1];
for(int i= 1; i<=N; i++){
g[i] = new ArrayList<>();
rg[i] = new ArrayList<>();
}
while(M-->0){
int u = read();
int v = read();
int w = read();
g[u].add(new int[]{v,w});
rg[v].add(new int[]{u,w});
}
long[] distNX = dijkstra(g);
long[] distXN = dijkstra(rg);
for(int i = 1; i<=N; i++){
distNX[i] += distXN[i];
}
long max = 0;
for(int i = 1; i<=N; i++){
if(i == X)
continue;
if(distNX[i] > max){
max = distNX[i];
}
}
System.out.print(max);
}
}사고의 흐름 및 풀이
개의 각 정점에서 번 정점까지 왕복하여 최단 시간으로 이동한다고 할 때, 가장 많은 시간이 걸리는 정점의 왕복 시간을 구하기
방향 그래프로 주어지고 구해야 하는건 각 N에서 X로 갔다가 X에서 각 N으로 오는 것을 더해야 함.
1) N->X
각 N에서 X로 가는건 정방향 그래프로 하면 N번 해서 구해야 하지만
역방향 그래프로 하면 사실 N->X로 진행하나 X->N으로 진행했을 때 최단거리는 같음
-> 모든 간선의 방향을 뒤집게 되면 원래 그래프의 N->X 경로는 역그래프의 X->N 경로와 정확히 대응함.
역방향 그래프를 하나 더 입력받아서 거기서 X->N 다익스트라로 dist 배열을 구하면 N->X 거리를 구한 것과 같음.
2) X->N
X에서 각 N으로 가는건 그냥 X에서 시작해서 모든 정점 N개에 도착하는걸 구하면 됨.
-> 정방향 그래프에서 X->N 다익스트라로 dist 배열 구하기
문제 - 간선의 길이를 2배 늘리기
간선의 길이를 2배 늘리기 설명 | 코드트리
간선의 길이를 2배 늘리기의 요구사항을 정확히 분석하고, 적절한 알고리즘을 고안해 두 번째 단계 중급 문제를 해결해보세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N, M;
static ArrayList<int[]>[] g;
static HashMap<Long, Integer> map;
static final long INF = 25_000L * 1_000_000 + 1;
static long[] dijkstra(int si, boolean isSecond, long key){
long[] dist = new long[N+1];
Arrays.fill(dist, INF);
dist[si] = 0;
PriorityQueue<long[]> q = new PriorityQueue<>(Comparator.comparingLong(a->a[1]));
q.add(new long[]{si, 0});
while(!q.isEmpty()){
long[] cur = q.poll();
int ci = (int) cur[0];
long cd = cur[1];
if(dist[ci] != cd)
continue;
for(int[] n : g[ci]){
int ni = n[0];
int nd = n[1];
// 비교하기 전에 2배 간선 가중치 해야함..
if(isSecond){
int[] rst = ltoi(key);
if((ci == rst[0] && ni == rst[1]) || (ci == rst[1] && ni == rst[0]))
nd += map.get(key);
}
if(dist[ni] > dist[ci] + nd){
dist[ni] = dist[ci] + nd;
q.add(new long[]{(long) ni, dist[ni]});
}
}
}
return dist;
}
static long itol(int i, int j){
return ((long) i)<<32 | j;
}
static int[] ltoi(long key){
int[] rst = new int[2];
rst[0] = (int) (key >> 32);
rst[1] = (int)(key - ((key >> 32) << 32));
return rst;
}
public static void main(String[] args) throws IOException{
N = read();
M = read();
int[][] li = new int[N+1][N+1];
g = new ArrayList[N+1];
for(int i = 1; i<=N; i++)
g[i] = new ArrayList<>();
while(M-->0){
int i = read();
int j = read();
int w = read();
li[i][j] = li[j][i] = w;
g[i].add(new int[]{j,w});
g[j].add(new int[]{i,w});
}
long[] distSI = dijkstra(1, false, 0);
map = new HashMap<>();
int cur = N;
while(cur != 1){
for(int[] n : g[cur]){
int ni = n[0];
int nd = n[1];
if(distSI[cur] == distSI[ni] + nd){
map.put(itol(cur,ni), nd);
cur = ni;
}
}
}
long max = 0;
for(long k : map.keySet()){
max = Math.max(max, dijkstra(1, true, k)[N]);
}
System.out.print(max - distSI[N]);
}
}사고의 흐름
처음에는 1->i, j->N 거리 구해놓고 모든 간선에 대해 순회할때 1->i + 2*(i,j) + j->N 을 max로 max - distSE[N] 이렇게 생각했었다.
문제는 양방향 그래프라 j->i도 고려해야 하고 i,j 간선이 2배가 됬을때 최단경로 자체가 달라질 수 있다는 거였음.
그리고 모든 간선에 대해서 보는게 아니라 최단 경로가 바뀌려면 최단경로상에 있는 간선들만 보면 됨.
풀이
먼저 i->N 방향의 다익스트라 최단거리를 구하고 해당 배열로부터 최단 경로 위의 간선들을 map 형태로 저장함
그리고 해당 간선만 2배를 한 그래프에서 다익스트라를 간선 갯수만큼 돌려주면 됨.
-> 여기서 다익스트라 relaxation을 위해 dist[ni] 와 dist[ci] + nd 조건비교를 하기 전에
반드시 간선 nd를 2배를 먼저 해 주고 갱신해야 함.
문제 - 백투더 블랫 닷( 실수 )
빽 투더 블랙 닷 2 설명 | 코드트리
빽 투더 블랙 닷 2의 요구사항을 정확히 분석하고, 적절한 알고리즘을 고안해 두 번째 단계 중급 문제를 해결해보세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N,M;
static int A,B;
static ArrayList<int[]>[] g;
static final int INF = 1000 * 100_000 + 1;
static int[] dijkstra(int si){
int[] dist =new int[N+1];
Arrays.fill(dist, INF);
dist[si] = 0;
PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(a->a[1]));
q.add(new int[]{si, 0});
while(!q.isEmpty()){
int[] cur = q.poll();
int ci = cur[0];
int cd = cur[1];
if(dist[ci] != cd)
continue;
for(int[] n : g[ci]){
int ni = n[0];
int nd = n[1];
if(dist[ni] > dist[ci] + nd){
dist[ni] = dist[ci] + nd;
q.add(new int[]{ni, dist[ni]});
}
}
}
return dist;
}
public static void main(String[] args) throws IOException{
N = read();
M = read();
A = read();
B = read();
g =new ArrayList[N+1];
for(int i = 1; i<=N; i++)
g[i] = new ArrayList<>();
while(M-->0){
int i = read();
int j = read();
int w = read();
g[i].add(new int[]{j,w});
g[j].add(new int[]{i,w});
}
int[] distSA = dijkstra(A);
int[] distSB = dijkstra(B);
int red = distSA[B];
int min = INF;
for(int i = 1; i<=N; i++){
if(i == A || i == B)
continue;
if(distSA[i] == INF || distSB[i] == INF)
continue;
min = Math.min(min, distSA[i] + distSB[i]+red);
}
System.out.print(min == INF ? -1 : min);
}
}사고의 흐름 및 풀이
dist(1, N) = dist(1, A) + dist(A, B) + dist(B, N) 으로 이루어지므로 빨간점 두개인 A,B 를 모두 거치면서
시작점인 i로 돌아오는 최단 거리는 다음과 같이 표현할 수 있음
dist(i, A) + dist(A,B) + dist(B, i)
-> distSA[i] (A에서 i 의 최단 거리) + distSA[B] (A에서 시작하므로) + distSB[i] (B에서 i의 최단 거리)
'공부 > 알고리즘' 카테고리의 다른 글
| [코드트리] 10 - DP, 비트마스킹 (0) | 2026.07.02 |
|---|---|
| [코드트리] 9 - DP, 구간합 DP (0) | 2026.07.01 |
| [코드트리] 8 - DP, Bitonic Cycle (0) | 2026.06.29 |
| [코드트리] 7 - Topological Sort, DAG DP (0) | 2026.06.22 |
| [코드트리] 6 - 청약 통장 코딩테스트 7주 공부 완주 회고, MST (0) | 2026.06.21 |