골드에그

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. 문제요약

9376번: 탈옥 (acmicpc.net)

W x H 크기의 직사각형 감옥이 있다. 이 감옥에는 두 명의 죄수가 있는데 이 두 죄수를 탈출시키기 위해서 열어야 하는 문의 최소 개수값은 얼마인지 구하시오. 빈 공간은 '.', 지나갈 수 없는 벽은 '*', 문은 '#', 죄수의 위치는 '$'이다. 문은 한 번 열리면 계속 열린 상태가 된다. 각 죄수와 감옥의 바깥을 연결하는 경로가 항상 존재하는 경우만 입력으로 주어진다. (죄수 - 감옥 - 죄수 모두 연결 상태)

2. 문제예제

3. 팩트추출

Fact 1 : Dijkstra 알고리즘 문제처럼 보인다. 그런데 출발지가 두 군데이고, 두 군데에서 같이 움직이면 BFS 의 경로 정보가 변질되어 버린다. [Programmers] 등산 코스 정하기 (Java) :: 골드에그 (tistory.com) 문제 같은 경우는 어디서 출발하던지 산봉우리에 도달하는 최소 경로만 찾으면 되므로 같이 움직여도 상관 없지만, 이 문제는 두 사람이 같은 경로로 탈출해야 한다는 점이 다르다.

같이 움직일 수 없다면 따로 움직여서 정보를 합쳐야 하는데 어떤 정보를 기준으로 합쳐야 할까?

어떠한 지점에서 BFS 최소 결과 값을 합친다면, 그 의미는 두 사람이 그 지점으로 만나기 위한 최소 값이다.

위 예제에서는 A 에서 1 로 가는 최소의 경로가 1 이고 B 에서 1 로 가는 최소의 경로가 2 인 것이다. A 와 B 가 만나기 위한 최소 값이라고 해석할 수 있다. 그런데 이 정보만으로는 부족하다. 탈출하기 위한 루트가 포함되지 않았다. A 와 B 는 만났지만, 탈출하기 위한 최소값이라고 볼 수는 없다.

탈출하기 위한 경로를 계산하려면, 탈출구에서 해당 지점까지 가는 경로도 추가해야 한다.

모든 경로가 최소가 되려면, A 에서 1 지점까지 거리도, B 에서 1 지점까지 거리도, 1 지점에서 탈출구까지 거리도 모두 최소여야 하기 때문이다. 만나는 지점을 중심으로 생각해보면 쉽다.

Fact 2 : 탈출구에 대한 정보를 맵 입력을 받을 때 알 수 없으므로 원래 맵 크기보다 1사이즈 더 크게 만들어 탈출구에서 오는 길목을 만들어준다. 원래 맵 크기가 N X M 이라면 N+2 X M+2 크기의 맵에서 시작한다.

Fact 3 : 정보를 합칠 때 중요한 점은 중복 정보를 제거해야 한다는 것이다. 1 지점까지 가는데 어떤 정보들이 중복이 되는지 생각해보아야 한다. 지문에서 문이 한 번 열리면 계속 열린 상태가 된다고 하였으므로 세 정보를 합칠 때 문에서 중복 카운트는 빼주어야 한다. 여기서는 세 명이 만난다고 가정해도 되므로 -2 를 해주면 된다.

4. 문제풀이(수동)

위 팩트추출을 통해 알아본 알고리즘으로 첫 번째 예제를 풀어보면 다음과 같다.

5. 문제전략

문제 전략은 팩트 추출과 문제 풀이를 통해 알아보았다. 원래 맵 크기보다 한 사이즈 큰 맵을 준비하고, 탈출구에서 오는 최소 DFS 결과 값과 각 죄수들로부터 DFS 한 결과 값을 합쳐 최소 경로를 구한다.

6. 소스코드

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

public class Main {
    private static int row, column;
    private static char[][] map;
    private static Node[] prisoners;
    private static final int[] dx = { 0, 0, -1, 1 };
    private static final int[] dy = { 1, -1, 0, 0 };
    private static final char WALL = '*';
    private static final char DOOR = '#';
    private static final char PRISONER = '$';
    static class Node implements Comparable<Node>{
        int x, y, open;
        Node(int x, int y) {
            this.x = x;
            this.y = y;
            this.open = 0;
        }
        Node(int x, int y, int open) {
            this.x = x;
            this.y = y;
            this.open = open;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.open, o.open);
        }
    }
    private static int[][] bfs(Node start) {
        PriorityQueue<Node> queue = new PriorityQueue<>();
        int[][] visited = new int[row+2][column+2];
        for (int[] visit: visited) {
            Arrays.fill(visit, -1);
        }

        queue.offer(start);
        visited[start.x][start.y] = 0;

        while(!queue.isEmpty()) {
            Node current = queue.poll();
            for (int i = 0; i < 4; i++) {
                int neighborX = current.x + dx[i];
                int neighborY = current.y + dy[i];
                if(neighborX < 0 || neighborX >= row+2 || neighborY < 0 || neighborY >= column+2) continue;
                if(visited[neighborX][neighborY] != -1 || map[neighborX][neighborY] == WALL) continue;
                if(map[neighborX][neighborY] == DOOR) {
                    visited[neighborX][neighborY] = visited[current.x][current.y] + 1;
                    queue.offer(new Node(neighborX, neighborY, current.open + 1));
                } else {
                    visited[neighborX][neighborY] = visited[current.x][current.y];
                    queue.offer(new Node(neighborX, neighborY, current.open));
                }
            }
        }
        return visited;
    }
    private static int getSum(int[][] one, int[][] two, int[][] out) {
        int minSum = row * column;

        for (int i = 0; i < one.length; i++)
        {
            for (int j = 0; j < one[i].length; j++)
            {
                if (map[i][j] == WALL)
                    continue;
                if (one[i][j] == -1 && two[i][j] == -1 && out[i][j] == -1)
                    continue;
                int sum = one[i][j] + two[i][j] + out[i][j];
                if (map[i][j] == DOOR)
                {
                    sum -= 2;
                }
                if (minSum > sum)
                {
                    minSum = sum;
                }
            }
        }
        return (minSum);
    }

    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());

        while(testCase-- > 0) {
            st = new StringTokenizer(br.readLine());
            row = Integer.parseInt(st.nextToken());
            column = Integer.parseInt(st.nextToken());
            map = new char[row+2][column+2];
            int[][] prisonerOne, prisonerTwo, out;
            prisoners = new Node[2];
            int prisonersIndex = 0;

            for (int i = 0; i < row; i++) {
                char[] row = br.readLine().toCharArray();
                for (int j = 0; j < column; j++) {
                    if (row[j] == PRISONER) {
                        prisoners[prisonersIndex++] = new Node(i + 1, j + 1);
                    }
                    map[i+1][j+1] = row[j];
                }
            }
            out = bfs(new Node(0,0));
            prisonerOne = bfs(prisoners[0]);
            prisonerTwo = bfs(prisoners[1]);
            System.out.println(getSum(prisonerOne, prisonerTwo, out));
        }
    }
}

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();
    }
}