[프로그래머스] 미로 탈출(Java)

미로 탈출

해결 방법

다익스트라(dijkstra) 알고리즘을 사용하여 해결했습니다.^^

다익스트라(dijkstra) 알고리즘이란 출발 노드에서 모든 노드까지의 최단 거리를 구하는 알고리즘 입니다.
(쉽게 말해서, 출발 노드를 기준으로 최단거리를 구하는 알고리즘 입니다.)

단, 가중치가 항상 양수이고,
그래프가 사이클이 존재하면 안됩니다.

맨 처음에 저는 레버는 고려하지 않고
시작지점, 도착지점으로 문제를 처음에 해결했습니다… ㅠ0ㅠ

문제에서 출발 -> 레버 -> 도착 이렇게 이동하라고 했습니다..

레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다.

따라서 다음과 같이 2가지 경우에서 다익스트라 알고리즘을 사용하여 최단거리 구하면 됩니다.^^

1. 출발 -> 레버
2. 레버 -> 도착

풀이

import java.util.*;

class Solution {
    public int solution(String[] maps) {
        int answer = 0;
        int x = maps.length;
        int y = maps[0].length();

        // 출발점, 도착점
        int startX = 0;
        int startY = 0;
        int endX = 0;
        int endY = 0;
        int startXl = 0;
        int startYl = 0;
        // 2차원 배열로 미로 저장
        String[][] miro = new String[x][y];
        for(int i = 0; i < x; i++) {
            char[] chars = maps[i].toCharArray();
            for(int j = 0; j < y; j++) {
                if(chars[j] == 'S') {
                    startX = i;
                    startY = j;
                } else if (chars[j] == 'E') {
                    endX = i;
                    endY = j;
                } else if(chars[j] == 'L') {
                    startXl = i;
                    startYl = j;
                }
                miro[i][j] = String.valueOf(chars[j]);
            }
        }

        // 인접 리스트 초기화
        List<Node>[][] list = new ArrayList[x][y];
        for(int i = 0; i < x; i++) {
            for(int j = 0; j < y; j++) {
                list[i][j] = new ArrayList<>();
            }
        }

        // 그래프로 변환
        for(int i = 0; i < x; i++) {
            for(int j = 0; j < y; j++) {
                if(!miro[i][j].equals("X")) {
                    list[i][j].add(new Node(i, j, 1));
                }
            }
        }

        // 시작점에서 레버까지 최단경로
        int dijkstra1 = dijkstra(list, miro, startX, startY, startXl, startYl, x, y);
        if(dijkstra1 == Integer.MAX_VALUE) return -1;

        // 레버에서 도착점까지 최단경로
        int dijkstra2 = dijkstra(list, miro, startXl, startYl, endX, endY, x, y);
        if(dijkstra2 == Integer.MAX_VALUE) return -1;

        answer = dijkstra1 + dijkstra2;

        return answer;
    }

    private int dijkstra(List<Node>[][] list, String[][] miro, int startX, int startY, int endX, int endY, int x, int y) {
        Queue<Node> pq = new PriorityQueue<>(
                (o1, o2) -> Integer.compare(o1.getWeight(), o2.getWeight())
        );

        // 최단거리 배열 초기화
        int[][] result = new int[x][y];
        for(int i = 0; i < x; i++) {
            for(int j = 0; j < y; j++) {
                result[i][j] = Integer.MAX_VALUE;
            }
        }

        // 출발 지점 설정
        result[startX][startY] = 0;
        pq.add(new Node(startX, startY, result[startX][startY]));

        // 방문 이력 배열
        boolean[][] visited = new boolean[x][y];
        visited[startX][startY] = true;

        while (!pq.isEmpty()) {
            Node poll = pq.poll();
            // 상, 하, 좌, 우
            int[] ud = {1, -1, 0, 0};
            int[] lr = {0, 0, 1, -1};
            for(int i = 0; i < 4; i++) {
                int newX = poll.getX() + ud[i];
                int newY = poll.getY() + lr[i];

                // 범위 체크
                if(newX < 0 || newY < 0 || newX >= x || newY >= y) {
                    continue;
                }

                for(Node node : list[newX][newY]) {
                    // 방문 이력이 없으면
                    if(!visited[node.getX()][node.getY()] && !miro[node.getX()][node.getY()].equals("X")) {
                        // 최소 비용 계산(선택한 노드 거리 + 선택한 노드의 엣지 가중치, 연결 노드의 최단 거리)
                        int min = Math.min(result[poll.getX()][poll.getY()] + node.getWeight(), result[node.getX()][node.getY()]);
                        result[node.getX()][node.getY()] = min;
                        // 방문 기록
                        visited[newX][newY] = true;
                        // 큐에 삽입
                        pq.add(new Node(newX, newY, min));
                    }
                }
            }
        }
        return result[endX][endY];
    }
}

class Node {
    private int x;
    private int y;
    private int weight;

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

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public int getWeight() {
        return weight;
    }
}