👨💻 문제
✍️ 풀이
단순히 보면 BFS로 풀어도 좋은 문제이지만,
낭떠러지를 통해 떨어지는 경우,
떨어져서 도달하는 위치를 확인하는 연산을 반복하게 될 수 있기 때문에,
각 칸에서 갈 수 있는 칸들을 모두 지정해놓고,
다익스트라를 통해 문제를 해결해야 한다.
🧵 그래프 구현
2차원 배열을 그래프로 변환해야 한다.
2차원 배열을 순회하며 해당 칸의 값에 따라 그래프를 구성한다.
고양이의 움직임은 크게 3가지가 있다.
1. 좌우
바닥이 존재할 경우 양 옆으로 이동할 수 있다.
비용 :1private static void connectBesides(int r, int c) { int idx = getIndexOfCoordinate(r, c); if (c-1 >= 0 && values[r][c-1] != 'D') { nodes[idx].add(new Node(idx-1, 1)); } if (c+1 < C && values[r][c+1] != 'D') { nodes[idx].add(new Node(idx+1, 1)); } }
2. 상하
사다리가 있다면 위 칸에서 현재 칸으로, 현재 칸에서 위 칸으로 이동할 수 있다.
비용 :5private static void connectLadder(int r, int c) { int idx = getIndexOfCoordinate(r, c); if (r-1 >= 0 && values[r-1][c] != 'X' && values[r-1][c] != 'D') { nodes[idx].add(new Node(idx-C, 5)); nodes[idx-C].add(new Node(idx, 5)); } }
3. 낙하
바닥이 없는 경우 낙하한다.
비용 :10private static void connectFall(int r, int c) { int fromIdx = getIndexOfCoordinate(r, c); while (values[++r][c] == 'X') {}; if (values[r][c] == 'D') { return; } int toIdx = getIndexOfCoordinate(r, c); nodes[fromIdx].add(new Node(toIdx, 10)); }
🏃♂️ 다익스트라
이제 구현해놓은 그래프로 다익스트라 알고리즘을 실행한다.
private static void dijkstra() {
dists = new int[R * C];
Arrays.fill(dists, INF);
pq.add(new Node(start, 0));
dists[start] = 0;
while(!pq.isEmpty()) {
Node node = pq.poll();
// System.out.printf("(%d,%d) : %d\n", node.idx/C, node.idx%C, node.cost);
if (node.idx == end) {
return;
}
if (dists[node.idx] < node.cost) { // isVisitedAlready
continue;
}
for (Node nextNode : nodes[node.idx]) {
if (dists[nextNode.idx] > nextNode.cost + node.cost) {
dists[nextNode.idx] = nextNode.cost + node.cost;
// System.out.printf(" (%d,%d) : %d\n", nextNode.idx/C, nextNode.idx%C, dists[nextNode.idx]);
pq.add(new Node(nextNode.idx, dists[nextNode.idx]));
}
}
}
}⚠️ 주의사항
겪었던 반례들이다.
1. X 바로 아래에 L이 있는 경우
L에서X로 오르내릴 수 있도록 한다면
X로부터L로 떨어지는 최단거리가10이 아닌5가 된다.
L위에X가 있다면 연결하지 않는다.
2. L 위에 D가 있는 경우
X나F를 통해D로 도달해도D에서부터는 갈 곳이 없기에 괜찮다고 생각했는데,
L에서 위에D가 있다면 오르내리도록 연결을 해버린다.
L에서D로의 연결을 막으면 해결된다.근데 그냥 불필요한 방문 횟수를 줄이기 위해
그냥D로는 어떤 경로로든 도달하지 못하도록 다 막았다.
📄 전체 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class _22955 {
private static final int INF = Integer.MAX_VALUE;
private static int R, C;
private static char[][] values;
private static int start, end;
private static ArrayList<Node>[] nodes;
private static PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.cost - b.cost);
private static int[] dists;
private static class Node {
int idx;
int cost;
public Node(int idx, int cost) {
this.idx = idx;
this.cost = cost;
}
}
public static void main(String[] args) throws IOException {
input();
switchToGraph();
dijkstra();
System.out.println(dists[end] == INF ? "dodo sad" : dists[end]);
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
values = new char[R][C];
for (int r=0; r<R; r++) {
String str = br.readLine();
for (int c=0; c<C; c++) {
values[r][c] = str.charAt(c);
}
}
}
private static void switchToGraph() {
nodes = new ArrayList[R * C];
for (int i=0; i<R*C; i++) {
nodes[i] = new ArrayList<>();
}
for (int r=0; r<R; r++) {
for (int c=0; c<C; c++) {
switch(values[r][c]) {
case 'C' :
start = getIndexOfCoordinate(r, c);
connectBesides(r, c);
break;
case 'L' :
connectLadder(r, c);
connectBesides(r, c);
break;
case 'F' :
connectBesides(r, c);
break;
case 'X' :
connectFall(r, c);
break;
case 'E' :
end = getIndexOfCoordinate(r, c);
break;
case 'D' :
break;
}
}
}
}
private static void connectBesides(int r, int c) {
int idx = getIndexOfCoordinate(r, c);
if (c-1 >= 0 && values[r][c-1] != 'D') {
nodes[idx].add(new Node(idx-1, 1));
}
if (c+1 < C && values[r][c+1] != 'D') {
nodes[idx].add(new Node(idx+1, 1));
}
}
private static void connectLadder(int r, int c) {
int idx = getIndexOfCoordinate(r, c);
if (r-1 >= 0 && values[r-1][c] != 'X' && values[r-1][c] != 'D') {
nodes[idx].add(new Node(idx-C, 5));
nodes[idx-C].add(new Node(idx, 5));
}
}
private static void connectFall(int r, int c) {
int fromIdx = getIndexOfCoordinate(r, c);
while (values[++r][c] == 'X') {};
if (values[r][c] == 'D') {
return;
}
int toIdx = getIndexOfCoordinate(r, c);
nodes[fromIdx].add(new Node(toIdx, 10));
}
private static int getIndexOfCoordinate(int r, int c) {
return r * C + c;
}
private static void dijkstra() {
dists = new int[R * C];
Arrays.fill(dists, INF);
pq.add(new Node(start, 0));
dists[start] = 0;
while(!pq.isEmpty()) {
Node node = pq.poll();
// System.out.printf("(%d,%d) : %d\n", node.idx/C, node.idx%C, node.cost);
if (node.idx == end) {
return;
}
if (dists[node.idx] < node.cost) { // isVisitedAlready
continue;
}
for (Node nextNode : nodes[node.idx]) {
if (dists[nextNode.idx] > nextNode.cost + node.cost) {
dists[nextNode.idx] = nextNode.cost + node.cost;
// System.out.printf(" (%d,%d) : %d\n", nextNode.idx/C, nextNode.idx%C, dists[nextNode.idx]);
pq.add(new Node(nextNode.idx, dists[nextNode.idx]));
}
}
}
}
}
입니다.