N x N 크기의 격자 형태의 board가 존재하고 각 격자의 칸은 0 또는 1로 채워져 있으며, 0은 칸이 비어있음을 1은 해당 칸이 벽으로 채워져 있음을 나타낸다.
시작점은 (0,0) 칸(좌측 상단), 도착점은 (N-1, N-1)(우측 하단)이다.
직선 도로와 코너가 존재한다. 직선 도로는 상하 또는 좌우로 연결한 경주로를 의미하고 두 직선 도로가 직각으로 만다는 지점을 코너라고 한다.
직선 도로 하나를 만들 때는 100원이 소요되며, 코너를 하나 만들 때는 500원이 추가로 든다.
경주로를 건설하는데 들어가는 최소 비용은?
가중치가 존재하는 최단 거리 문제이다. 최소 비용을 구하기 위해서는 추가 금액이 들어가는 코너를 최소한으로 써야지 가능할 것 같다.
코너의 판정은 어떻게 해야 할까? 코너는 결국 이동 방향이 변경됐다는 것이다. 따라서 직전 이동 방향과 이번 이동 뱡향을 알면 코너인지를 판단할 수 있다. 즉 이전과 방향이 다르면 코너다.
좌우의 경우도 방향이 다르다. 하지만 이 경우는 코너가 아니다. 그런데 어차피 이 경우는 생각하지 않아도 된다. 최단거리를 찾는데 돌아가는 경우는 없다.
풀이를 생각해보자. 우선 가중치가 있는 최단거리를 구해야 하는 문제이다. 다익스트라로 풀 수 있을까?
다익스트라의 PriorityQueue에 넣을 때 방향도 함께 넣어서 방향별로 다른 경로로 판정하면 가능할 것 같다.
import java.util.*;
class Solution {
static class Node {
int r;
int c;
int dir;
int cost;
public Node(int r, int c, int dir, int cost) {
this.r = r;
this.c = c;
this.dir = dir;
this.cost = cost;
}
}
static final int INF = Integer.MAX_VALUE;
static int[] dr = {-1, 1, 0, 0}; //상하좌우
static int[] dc = {0, 0, -1, 1};
static int[][] distances;
public int solution(int[][] board) {
int N = board.length;
distances = new int[N][N];
for (int[] row : distances) {
Arrays.fill(row, INF);
}
distances[0][0] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.cost));
pq.add(new Node(0, 0, 1, 0));
pq.add(new Node(0, 0, 3, 0));
while(!pq.isEmpty()) {
Node curr = pq.poll();
int r = curr.r;
int c = curr.c;
int dir = curr.dir;
int cost = curr.cost;
if (distances[r][c] < cost) continue;
for (int d = 0; d < 4; d++) {
int weight = 100;
int nr = r + dr[d];
int nc = c + dc[d];
if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
if (board[nr][nc] == 1) continue;
if (dir != d) {
weight += 500;
}
if (distances[nr][nc] > distances[r][c] + weight) {
distances[nr][nc] = distances[r][c] + weight;
pq.add(new Node(nr, nc, d, distances[nr][nc]));
}
}
}
int answer = distances[N-1][N-1];
return answer;
}
}
이렇게 풀었는데 오답이 됐다. 왜 틀렸는지 분석해 보자.
가장 큰 문제는 int [][] distances 배열이다.
나는 처음에는 직선으로 도착하거나 코너로 도착하거나 둘 중 하나이니까 그 두 경우를 전부 pq에 넣으면 어차피 저렴한 걸로 갱신되지 않을까 생각했다. 그런데 이렇게 풀게 되면 그 지점까지의 최솟값이 최종적인 최솟값이라고 보장이 돼야 한다. 하지만 이 문제는 그렇지 않다.
이렇게 관리하게 되면 같은 위치라도 다른 방향으로 도착했을 때의 비용 차이를 반영하지 못한다.
결과적으로, 특정 위치에 더 높은 비용으로 도착했지만, 방향이 달라서 이후 경로에서 더 낮은 총비용을 가질 수 있는 경우를 놓치게 되는 것이다.
이를 해결하기 위해 int [][][] distances로 3차원으로 방향까지 관리하도록 하겠다.
import java.util.*;
class Solution {
static class Node {
int r;
int c;
int dir;
int cost;
public Node(int r, int c, int dir, int cost) {
this.r = r;
this.c = c;
this.dir = dir;
this.cost = cost;
}
}
static final int INF = Integer.MAX_VALUE;
static int[] dr = {-1, 1, 0, 0}; //상하좌우
static int[] dc = {0, 0, -1, 1};
static int[][][] distances;
public int solution(int[][] board) {
int N = board.length;
distances = new int[4][N][N];
for (int d = 0; d < 4; d++) {
for (int[] row : distances[d]) {
Arrays.fill(row, INF);
}
}
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.cost));
for (int d = 0; d < 4; d++) {
distances[d][0][0] = 0;
pq.add(new Node(0, 0, d, 0));
}
while(!pq.isEmpty()) {
Node curr = pq.poll();
int r = curr.r;
int c = curr.c;
int dir = curr.dir;
int cost = curr.cost;
if (distances[dir][r][c] < cost) continue;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
int weight = 100;
if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
if (board[nr][nc] == 1) continue;
if (dir != d) {
weight += 500;
}
if (distances[d][nr][nc] > distances[dir][r][c] + weight) {
distances[d][nr][nc] = distances[dir][r][c] + weight;
pq.add(new Node(nr, nc, d, distances[d][nr][nc]));
}
}
}
int answer = INF;
for (int d = 0; d < 4; d++) {
answer = Math.min(answer, distances[d][N-1][N-1]);
}
return answer;
}
}
미로 1칸을 이동하는 것을 1초라고 가정했을 때 최대한 빠르게 미로를 빠져나가는 데 걸리는 시간을 구하는 것이다.
즉 최단거리를 구해야 하고 BFS를 사용하면 될 것 같다.
탈출하지 못한 경우 -1을 반환하면 된다.
우선 주어진 배열은 String [ ] maps이다. 문자열로 “SOOOL” 이런 식으로 값이 들어가 있다.
S는 출발지, E 출구, L 레버, O 통로, X 벽이다.
문자열이라는 것은 결국 char []을 다루는 것과 동일하다.
또한 시간을 저장하기 위한 별도의 배열이 필요하다 이 배열은 시작 위치에서부터 탐색이 될수록 1씩 증가시켜 가며 값을 저장할 것이다.
출발지 → 레버로 도달하지 못하면 -1을 반환한다.
그 후 레버 → 출구 과정에서 도달하지 못하면 마찬가지로 -1을 반환한다.
최종 풀이는 다음과 같다.
S에서 L까지 BFS를 통해 걸리는 최소 시간을 구한다.
L에서 O를 목표로 BFS를 통해 걸리는 최소 시간을 구한다.
두 최소 시간을 통해 정답을 반환한다.
import java.util.*;
class Solution {
static class Point {
int r;
int c;
public Point(int r, int c) {
this.r = r;
this.c = c;
}
// 편의상 간단하게 구현
@Override
public boolean equals(Object o) {
Point other = (Point) o;
return r == other.r && c == other.c;
}
}
static final int[] DR = {-1, 1, 0, 0};
static final int[] DC = {0, 0, -1, 1};
static Point start;
static Point lever;
static Point goal;
public int solution(String[] maps) {
int startToLever = 0;
int leverToGoal = 0;
for (int row = 0; row < maps.length; row++) {
for (int col = 0; col < maps[row].length(); col++) {
switch (maps[row].charAt(col)) {
case 'S' -> start = new Point(row, col);
case 'L' -> lever = new Point(row, col);
case 'E' -> goal = new Point(row, col);
}
}
}
startToLever = bfs(start, lever, maps);
leverToGoal = bfs(lever, goal, maps);
// 도달하지 못하는 경우
if (startToLever == 0 || leverToGoal == 0) return -1;
return startToLever + leverToGoal;
}
private int bfs(Point start, Point goal, String[] maps) {
int[][] times = new int[maps.length][maps[0].length()];
Queue<Point> q = new LinkedList<>();
q.add(start);
while (!q.isEmpty()) {
Point curr = q.poll();
if (curr.equals(goal)) {
return times[curr.r][curr.c];
}
for (int d = 0; d < 4; d++) {
int nr = curr.r + DR[d];
int nc = curr.c + DC[d];
if (nr < 0 || nr >= maps.length || nc < 0 || nc >= maps[nr].length()) continue;
if (maps[nr].charAt(nc) == 'X') continue;
if (times[nr][nc] != 0) continue;
times[nr][nc] = times[curr.r][curr.c] + 1;
q.add(new Point(nr, nc));
}
}
return 0; // goal에 도달하지 못한 경우
}
}
방문 판단을 times 배열의 값으로 하고 있는데 시작점을 별도로 방문처리 하지 않았다.
이는 어차피 방문 지점을 BFS로 재방문한다 해도 답에 영향이 없기 때문에 최종 답 처리 편의를 위해 방문처리를 생략했다.
import java.util.*;
class Solution {
static int[] DR = {-1, 1, 0, 0}; // 상하좌우 기준
static int[] DC = {0, 0, -1, 1};
public int solution(int[][] maps) {
int m = maps.length - 1;
int n = maps[0].length - 1;
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{0, 0}); // 시작점
while (!q.isEmpty()) {
int[] curr = q.poll();
int r = curr[0];
int c = curr[1];
if (r == m && c == n) {
return maps[r][c]; // 이미 도착지에 도달한 상황
}
for (int d = 0; d < 4; d++) {
int nr = r + DR[d];
int nc = c + DC[d];
if (nr < 0 || nr > m || nc < 0 || nc > n) continue;
if (maps[nr][nc] != 1) continue;
maps[nr][nc] = maps[r][c] + 1;
q.add(new int[]{nr, nc});
}
}
return maps[m][n] == 1 ? -1 : maps[m][n];
}
}
최소 비용을 구하는 문제이기 때문에 먼저 떠오르는 것은 cost가 저렴한 순으로 꺼내서 다리를 설치하는 것이다.
이때 만약 불필요한 다리라면 건설하지 않아야 한다. 여기서 불필요하다는 뜻은 해당 다리가 없어도 방문이 가능한 경우를 뜻한다.
여기서 이 판단을 하는 방법으로 집합을 쓰겠다. 같은 집합에 속한다면 즉 루트가 같다면 해당 집합은 모두 방문이 가능한 상태가 된다.
알고리즘의 초안은 다음과 같다.
최소 비용의 다리를 꺼낸다. → PriorityQueue를 사용하면 간단해진다.
이 다리에 추가되는 섬이 이미 같은 집합에 존재하면 다리를 설치하지 않는다. → 설치되는 경우 두 섬을 Union 연산을 통해 같은 집합으로 만든다.
pq가 비게 될 때까지 반복한다.
결국 Union-Find만 잘 구현하면 해결되는 문제다.
우선 Union-Find의 코드부터 보고 이해해 보자.
Union연산은 두 집합을 하나로 합치는 연산이고 Find는 특정 요소가 속하는 집합의 루트(대표)를 찾는 연산이다. 이 알고리즘은 주로 트리 구조를 사용하여 집합을 표현하게 된다.
public class UnionFind {
private int[] parent; // 각 요소의 부모를 저장하는 배열
private int[] rank; // 트리의 높이를 저장하는 배열
// 생성자: n개의 요소를 각각 독립된 집합으로 초기화
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for(int i = 0; i < n; i++) {
parent[i] = i; // 초기에는 각 요소가 자기 자신을 부모로 가짐
rank[i] = 1; // 초기 트리의 높이는 1로 설정. 0으로 하는 경우도 있다.
}
}
// Find 연산: x가 속한 집합의 대표(루트)를 찾음
public int find(int x) {
if(parent[x] != x) {
parent[x] = find(parent[x]); // 경로 압축
}
return parent[x];
}
// Union 연산: x가 속한 집합과 y가 속한 집합을 합침
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if(rootX == rootY) {
return; // 이미 같은 집합에 속해 있음
}
// 랭크를 비교하여 트리의 높이를 최소화
if(rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if(rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX] += 1; // 트리의 높이가 증가
}
}
// 두 요소가 같은 집합에 속해 있는지 확인
public boolean connected(int x, int y) {
return find(x) == find(y);
}
}
이해하기 어려운 알고리즘은 아니다. 여기서 주목해야 할 부분이 두 가지 있다.
경로 압축 parent 배열은 자신의 부모 노드를 가지고 있다. parent [idx]가 idx의 부모를 뜻한다. 하지만 바로 자신의 부모를 가지고 있으면 탐색에 시간이 증가하게 된다. 이를 효율화하기 위해 자신의 부모가 아닌 집합의 루트를 가지고 있게 하는 방식이 경로 압축이다.
Rank 개념 트리의 높이가 커질수록 연산이 비효율적이 됩니다. 따라서 Rank의 개념을 도입해 높이를 최소화한다. Union 연산 시, 두 집합의 트리 높이를 비교하여 작은 트리를 큰 트리 아래에 합친다. 높이가 같다면 어디에 합쳐도 상관없다.
이 알고리즘을 통해 문제를 다음과 같이 풀 수 있습니다.
import java.util.*;
class Solution {
public int solution(int n, int[][] costs) {
int[] parent = new int[n];
int[] rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
int answer = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
for (int[] info : costs) {
pq.add(info);
}
while (!pq.isEmpty()) {
int[] info = pq.poll();
int id1 = info[0];
int id2 = info[1];
int cost = info[2];
// 이미 같은 집합에 속해있다면 다리를 놓는것은 낭비다.
if (find(id1, parent) == find(id2, parent)) continue;
union(id1, id2, parent, rank);
answer += cost;
}
return answer;
}
private int find(int x, int[] parent) {
if (x != parent[x]) {
parent[x] = find(parent[x], parent);
}
return parent[x];
}
private void union(int x, int y, int[] parent, int[] rank) {
int rootX = find(x, parent);
int rootY = find(y, parent);
if (rootX == rootY) return;
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
