[프로그래머스] 159993 미로 탈출 - JAVA - Lv.2

[프로그래머스] 159993 미로 탈출 - JAVA - Lv.2

문제

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

프로그래머스

문제 분석

조건

• 문자열로 주어진 `maps`에서 S좌표에서 L좌표로, 그후 E좌표로 이동하는 최단 거리를 구하는 문제이다.
• 같은 좌표를 다시 지날 수 있으며 S좌표에서 L좌표로 이동할 때 E좌표를 지날 수 있다.
• L좌표에서 E좌표로 이동할때도 S좌표를 지날 수 있다.
• 1칸 이동할 때 1초가 걸릴때, 최단 시간을 구하기.

풀이방법

• 최단거리를 구하는 문제이므로 bfs를 이용한다.
• 좌표와 카운트를 변수로 가지는 Node 클래스를 만들어 문제를 해결했다.
• bfs를 2번 이용하여 S>L, L>E 순으로 횟수를 구하였다.
• L좌표에 도착하였다면 `visited`배열과 `que`를 초기화 해주었다.
  • L좌표에 가는 경로에 E좌표가 없었다면 `visited`를 초기화를 하지 않아도 되지만 채점 기준에 효율성 테스트가 없어서 따로 체크하지 않았다.

코드

import java.util.*;

class Solution {
    public int solution(String[] maps) {
        int answer = 0;
        char[][] map = new char[maps.length][maps[0].length()];
        boolean[][] visited = new boolean[map.length][map[0].length];

        Node start = null;
        Node lever = null;
        for (int r = 0; r < maps.length; r++) {
            for (int c = 0; c < maps[0].length(); c++) {
                map[r][c] = maps[r].charAt(c);
                if (map[r][c] == 'S') {
                    start = new Node(r, c, 0);
                    visited[r][c] = true;
                    map[r][c] = 'S';
                } else if (map[r][c] == 'L') {
                    lever = new Node(r, c);
                }
            }
        }
        Deque<Node> que = new ArrayDeque<>();
        que.add(start);
        answer += bfs(map, visited, que, 'L');
        if (answer == -1) {
            return answer;
        }
        visited = new boolean[map.length][map[0].length];
        visited[lever.getR()][lever.getC()] = true;
        que = new ArrayDeque<>();
        que.add(lever);
        int temp = bfs(map, visited, que, 'E');
        if (temp == -1) {
            return -1;
        }
        return answer + temp;
    }

    private static int bfs(char[][] map, boolean[][] visited, Deque<Node> que, char find) {
        int[][] dr = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!que.isEmpty()) {
            Node now = que.pop();
            if (map[now.getR()][now.getC()] == find) {
                return now.getCount();
            }
            for (int[] d : dr) {
                int nextR = now.getR() + d[0];
                int nextC = now.getC() + d[1];
                if (nextR >= 0 && nextR < map.length && nextC >= 0 && nextC < map[0].length) {
                    if (map[nextR][nextC] == 'X' || visited[nextR][nextC]) {
                        continue;
                    }
                    visited[nextR][nextC] = true;
                    que.add(new Node(nextR, nextC, now.getCount() + 1));
                }
            }
        }
        return -1;
    }
}

class Node {
    private int r;
    private int c;
    private int count;

    public Node(int r, int c) {
        this.r = r;
        this.c = c;
        this.count = 0;
    }

    public Node(int r, int c, int count) {
        this.r = r;
        this.c = c;
        this.count = count;
    }

    public int getR() {
        return r;
    }

    public int getC() {
        return c;
    }

    public int getCount() {
        return count;
    }
}

결과