목차
1. 문제 설명
2. 접근 방식
3. 코드
1. 문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/67259
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr

경주로는 상, 하, 좌, 우로 인접한 두 빈 칸을 연결하여 건설할 수 있고, 벽이 있는 칸에는 경주로를 건설할 수 없다.
- 인접한 두 빈 칸을 상하 또는 좌우로 연결한 경주로를 직선 도로라고 한다. (개당 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
갱신한뒤, 우선순위큐에 해당 노드를 추가해 최소 비용을 기준으로 탐색을 이어나가도록했다.
'Problem Solving > Programmers' 카테고리의 다른 글
| [Algorithm] 홀짝트리 (0) | 2025.09.16 |
|---|---|
| [Algorithm] 여행경로 (1) | 2025.09.05 |
| [Algorithm] 서버 증설 횟수 (1) | 2025.09.02 |
| [SQL] 멸종위기의 대장균 찾기 문제 풀이 (0) | 2025.03.07 |
| [SQL] 대장균들의 자식의 수 구하기 문제 풀이 (4) | 2025.03.05 |