골드에그

1. 문제요약

24042번: 횡단보도 (acmicpc.net)

횡단보도에 파란불이 들어오면 반대편 지역으로 이동할 수 있으며 이동하는 데 1분이 걸린다. 1 + i ( 0 <= i < M) 번째 신호는 i, M+i, 2M+i, 3M+i, ... 분 주기에 시작해서 1분 동안 Ai 번 지역과 Bi 번 지역을 잇는 횡단보도에 파란불이 들어오고, 다른 모든 횡단보도에는 빨간불이 들어온다. 한 주기 동안 같은 횡단보도에 파란불이 여러 번 들어올 수 있다.

횡단보도와 신호의 정보가 주어질 때, 시간 0 분에서 시작해서 1 번 지역에서 N 번 지역까지 가는 최소 시간을 구하시오.

2. 문제예제

3. 문제풀이(수동)

예제 풀이 2번을 수동 풀이한다.

각 횡단보도가 켜지는 시간대는 위 표와 같다. 내가 만약 7 - 8 번 구간을 처음에 선택하였다면 그 다음 구간을 선택할 때 걸리는 시간이 시계방향처럼 연산된다. 그 다음 1 - 5 번 구간을 선택하면 +2 가 되고, 3 - 4 번 구간을 선택하면 한 바퀴 돌아서 +10 이 된다. 그 다음 구간의 시간 대가 현재 시간 대보다 적다면 한 바퀴 돌아서 연산된다.

그렇게 1번부터 8번까지 순회하는 길이 가장 빠른 구간은 다음과 같다.

1 - 2 >> 2 - 3 >> 3 - 4 >> 4 - 8 로 7 + 2 + 4 + 5 = 18 이다.

4. 팩트추출

Fact 1 : 최소 시간이 소요되는 구간을 찾는 문제로 다이젝스트라 알고리즘 문제다. 다만 일반적인 다이젝스트라와 다른 점은 거리 계산 시 그 다음 구간의 시간 대가 현재 시간 대보다 작으면 cost 값을 한 바퀴 돌아서 더해주어야 한다는 점이다.

5. 문제전략

다이젝스트라 응용 문제다.

6. 소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int N, M;
    private static List<List<Node>> crossWalk;
    private static long[] distance;
    static class Node implements Comparable<Node>{
        int index;
        long cost;
        Node(int index, long cost) {
            this.index = index;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return Long.compare(this.cost, o.cost);
        }
    }
    private static void dijkstra() {
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.offer(new Node(1, 0));
        distance[1] = 0;

        while(!queue.isEmpty()) {
            Node currentNode = queue.poll();
            if (currentNode.cost > distance[currentNode.index])
                continue;
            for (Node next :crossWalk.get(currentNode.index)) {
                int nextIndex = next.index;
                long nextCost;
                if (currentNode.cost <= next.cost) {
                    nextCost = next.cost + 1;
                } else {
                    // 모듈러 연산
                    nextCost = ((long) Math.ceil(((double)currentNode.cost-next.cost)/M)) * M + next.cost + 1;
                }
                if (nextCost < distance[nextIndex]) {
                    distance[nextIndex] = nextCost;
                    queue.offer(new Node(nextIndex, nextCost));
                }
            }
        }
    }
    public static void main(String[] args) throws Exception {
        StringTokenizer st;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        distance = new long[N+1];
        Arrays.fill(distance, Long.MAX_VALUE);

        crossWalk = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            crossWalk.add(new ArrayList<Node>());
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            crossWalk.get(u).add(new Node(v, i));
            crossWalk.get(v).add(new Node(u, i));
        }
        dijkstra();
        System.out.println(distance[N]);
    }
}

1. 문제요약

코딩테스트 연습 - 등산코스 정하기 | 프로그래머스 스쿨 (programmers.co.kr)

출입구에서 산봉우리까지 갔다가 다시 원래의 출입구로 돌아오는 등산코스를 정하려고 한다.

등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity 라고 할 때 이 intensity 가 가장 짧은 코스를 찾아라. (등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 한다.)

2. 문제예제

등산코스를 1-2-4-5-6-4-2-1 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같다.

각 경로의 가중치가 가장 큰 값이 3 이며, 이 보다 intensity가 낮은 등산코스는 없다.

3. 팩트추출

Fact 1 : Dijkstra 다이젝스트라 알고리즘처럼 항상 최단 거리를 선택한다면, 경로의 intensity 배열은 항상 단조 증가 형태이다. 이 점을 활용하면 출발점에서 산봉우리까지 갔다가 다시 출발점으로 돌아오지 않아도 된다. 출발점에서 산봉우리까지 가는 반쪽짜리 최단 경로만 찾으면 된다. 출발 경로와 회귀 경로가 틀릴 수 있을지 언정 intensity 는 같을 것이기 때문이다. 이 문제에서는 경로를 구하라고 하지 않았으므로 가능하다. => 따라서 큐에 꺼낸 위치가 산봉우리라면 탐색을 종료한다.

Fact 2 : Fact 1 과 마찬가지로 경로를 구하라고 하지는 않았으므로, 출발점에서 동시에 출발하여 intensity 배열을 수정하여도 상관이 없다. 문제에서 요구하는 정답은 산봉우리와 그 산봉우리의 intensity 이다. 그러니까 어느 출발점에서 출발하여도 도착지점의 intensity 가 최소가 되는 경로만 찾으면 된다. 따라서 우선순위 큐에 출발지점을 모두 넣어놓고 시작한다.

Fact 3 : 일반적인 Dijkstra 다이젝스트라 알고리즘과 다른 점은 각 지점의 비용을 합한 거리가 최소가 되는 경로를 찾는 것이 아니라 각 구간의 최대 비용이 최소가 되는 경로를 찾는 것이다. 따라서 아래와 같이 로직을 수정한다.

if(dist[adjNode.to] > curNode.weight + adjNode.weight){
	dist[adjNode.to] = curNode.weight + adjNode.weight;
}

↓↓↓↓↓↓

if (dist[adjNode.to] > Math.max(curNode.weight, adjNode.weight)) {
	dist[adjNode.to] = effort;
}

Fact 4 : 산봉우리까지 가는 intensity 가 같은 경로가 여러 개라면, 산봉우리의 번호가 가장 작은 것을 반환하라고 지문에서 나와있으므로 산봉우리-intensity 배열에서 최소값을 찾을 때 산봉우리 배열을 먼저 정렬해야 한다.

4. 문제전략

팩트추출에서 소개한 다이젝스트라 변형 알고리즘을 사용하면 된다.

5. 소스코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Solution {
    static class Node implements Comparable<Node> {
        int index;
        int effort;
        public Node(int index, int effort) {
            this.index = index;
            this.effort = effort;
        }
        @Override
        public int compareTo(Node o) {
            return this.effort - o.effort;
        }
    }
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static int[] efforts;
    static int[] gatesSave, summitsSave;
    private static void initGraph(int v, int[][] data) {
        for(int i=0; i < v+1; i++){
            graph.add(new ArrayList<>());
        }
        for (int[] datum : data) {
            graph.get(datum[0]).add(new Node(datum[1], datum[2]));
            graph.get(datum[1]).add(new Node(datum[0], datum[2]));
        }
        efforts = new int[v+1];
        for (int i = 1; i < v+1; i++) {
            efforts[i] = Integer.MAX_VALUE;
        }
    }

    private static int[] dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();

        // 시작지점 삽입
        for (int gate : gatesSave) {
            pq.offer(new Node(gate, 0));
            efforts[gate] = 0;
        }

        while (!pq.isEmpty()) {
            Node curNode = pq.poll();
            if (isSummit(curNode.index))
                continue;
            if (efforts[curNode.index] < curNode.effort) {
                continue;
            }
            for (Node adjNode : graph.get(curNode.index)) {
                int effort = (adjNode.effort == Integer.MAX_VALUE) ? curNode.effort : Math.max(curNode.effort, adjNode.effort);
                if (efforts[adjNode.index] > effort) {
                    efforts[adjNode.index] = effort;
                    pq.offer(new Node(adjNode.index, efforts[adjNode.index]));
                }
            }
        }

        Arrays.sort(summitsSave);
        int index = -1;
        int minEffort = Integer.MAX_VALUE;
        for (int summit : summitsSave) {
            if (efforts[summit] < minEffort) {
                minEffort = efforts[summit];
                index = summit;
            }
        }
        return new int[]{index, minEffort};
    }

    private static boolean isSummit(int num) {
        for (int summit : summitsSave) {
            if (num == summit) return true;
        }
        return false;
    }

    public static int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        gatesSave = gates;
        summitsSave = summits;
        initGraph(n, paths);
        return dijkstra();
    }
}