[Algorithm] 경주로 건설

목차

---

1. 문제 설명

2. 접근 방식

3. 코드

 

 

 

 

 

1. 문제 설명

---

https://school.programmers.co.kr/learn/courses/30/lessons/67259

프로그래머스

 

경주로는 상, 하, 좌, 우로 인접한 두 빈 칸을 연결하여 건설할 수 있고, 벽이 있는 칸에는 경주로를 건설할 수 없다. 

• 인접한 두 빈 칸을 상하 또는 좌우로 연결한 경주로를 직선 도로라고 한다. (개당 100원)
• 두 직선 도로가 서로 직각으로 만나는 지점을 코너라고 부른다. (개당 500원)

 

경주로를 건설하는데 필요한 최소 비용을 구하는 문제이다. 

이때 언제 코너가 만들어지는지 계산하려면 방향을 고려해야한다.

 

각 칸마다 비용이 동일하다면 bfs를 사용하면 되지만

직선도로는 100원 / 코너는 500원으로 비용이 다르기 때문에 가중치가 다른 간선의 최소 비용을 구하는 다익스트라를 적용해야 한다. 

 

 

2. 접근 방식

---

다익스트라를 적용하기 위해 우선순위큐에서 사용할 내부 클래스를 새로 정의한다. 

내부 클래스는 아래와 같은 정보를 저장해야 한다. 

 

① x좌표

② y좌표

③ 방향 정보

④ 현재 좌표까지의 최소 비용

 

이때 경주로는 인접한 두 칸만 연결할 수 있으므로 방향 정보는 다음과 같이 저장한다. 

상 (0)

하 (1)

좌 (1)

우 (1)

 

 

마찬가지로 인접한 두 칸을 연결한다는 뜻은, 방문 가능한 칸은 무조건 직선 도로라는 의미이다. 그렇다면 코너는 어떻게 식별할 수 있을까?

 

간단하다. 

 

우선순위큐에서 꺼낸 노드의 방향과 새롭게 만든 노드의 방향이 일치하는지만 검사하면 된다. 방향이 일치한다면 직선 도로만 해당되며, 방향이 일치하지 않는다면 직선 도로 + 코너인 것이다.  

 

다만 격자 도면이 1로 채워져 있다면 해당 칸은 벽이기 때문에 지나갈 수 없다.

 

 

 

이를 코드로 구현하면 다음과 같다. 

 

 

 

3. 코드

---

import java.util.*;

class Solution {
    public static class Node implements Comparable<Node> {
        int x; // x 좌표
        int y; // y 좌표
        int dir; // 방향 (0 : 상 / 1 : 하 / 2 : 좌 / 3 : 우)
        int cost; // 최소 비용

        public Node(int x, int y, int dir, int cost) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node n) {
            return Integer.compare(this.cost, n.cost);
        }
    }

    public static int[][][] distance;

    public int solution(int[][] board) {
        distance = new int[board.length][board.length][4];
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board.length; j++) {
                Arrays.fill(distance[i][j], Integer.MAX_VALUE);
            }
        }

        bfs(board);
        return Arrays.stream(distance[board.length - 1][board.length - 1])
                .min()
                .getAsInt();
    }

    public static void bfs(int[][] board) {
        int[] dX = { -1, 1, 0, 0 };
        int[] dY = { 0, 0, -1, 1 };

        PriorityQueue<Node> queue = new PriorityQueue();
        queue.add(new Node(0, 0, -1, 0));
        for(int i = 0; i < 4; i++) {
            distance[0][0][i] = 0;
        }

        while(!queue.isEmpty()) {
            Node node = queue.poll();

            for(int i = 0; i < 4; i++) {
                int newdX = node.x + dX[i];
                int newdY = node.y + dY[i];

                if(newdX < 0 || newdX >= board.length || newdY < 0 || newdY >= board.length) continue;
                if(board[newdX][newdY] == 1) continue;

                int newCost = node.cost + 100;
                if(node.dir != i && node.dir != -1) newCost += 500;
                
                if(distance[newdX][newdY][i] > newCost) {
                    distance[newdX][newdY][i] = newCost;
                    queue.add(new Node(newdX, newdY, i, distance[newdX][newdY][i]));
                }
            }
        }
    }
}

 

코드를 하나씩 뜯어보자. 

 

public static class Node implements Comparable<Node> {
    int x; // x 좌표
    int y; // y 좌표
    int dir; // 방향 (0 : 상 / 1 : 하 / 2 : 좌 / 3 : 우)
    int cost; // 최소 비용

    public Node(int x, int y, int dir, int cost) {
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.cost = cost;
    }

    @Override
    public int compareTo(Node n) {
        return Integer.compare(this.cost, n.cost);
    }
}

 

우선순위큐를 적용하기 위해 내부 클래스는 Comparable 구현체로 만들었다. 

최소 비용을 구하는 문제로, 정렬 조건은 현재 좌표까지 도달하는데 필요한 비용으로 삼았다. 

 

int[][][] distance = new int[board.length][board.length][4];
for(int i = 0; i < board.length; i++) {
    for(int j = 0; j < board.length; j++) {
        Arrays.fill(distance[i][j], Integer.MAX_VALUE);
    }
}

 

최종적으로 최소 비용을 저장하는 배열 distance를 만들었다. 

2차원 배열이 아닌 3차원 배열로 생성한 이유는 각 방향에서 만들어지는 최소 비용이 다를 수 있기 때문이다. 

따라서 상, 하, 좌, 우 총 4가지 방향을 고려하기 위해 마지막 차원으로 방향 정보를 저장하는 3차원 배열을 생성했다. 

 

while(!queue.isEmpty()) {
    Node node = queue.poll();

    for(int i = 0; i < 4; i++) {
        int newdX = node.x + dX[i];
        int newdY = node.y + dY[i];

        if(newdX < 0 || newdX >= board.length || newdY < 0 || newdY >= board.length) continue;
        if(board[newdX][newdY] == 1) continue;

        int newCost = node.cost + 100;
        if(node.dir != i && node.dir != -1) newCost += 500;

        if(distance[newdX][newdY][i] > newCost) {
            distance[newdX][newdY][i] = newCost;
            queue.add(new Node(newdX, newdY, i, distance[newdX][newdY][i]));
        }
    }
}

 

코너를 검사하기 위해 큐에서 뺀 노드의 방향과 새로운 노드의 방향을 비교한다. 

다만 시작점 (0, 0)은 어느 방향으로 가더라도 코너가 없기 때문에 node.dir이 -1인 경우는 제외한다. 

 

bfs처럼 처음 방문한 경로가 최소 비용이 보장되는 것은 아니므로 visited 배열은 사용하지 않는다.

대신 newCost를 계산한뒤 distance[newdX][newdY]가 갱신의 여지가 있다면

distance[newdX][newdY] > newCost

 

갱신한뒤, 우선순위큐에 해당 노드를 추가해 최소 비용을 기준으로 탐색을 이어나가도록했다.