프로그래머스 - 미로탈출

1. 문제

문제 설명

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

---

제한사항

• 5 ≤ maps의 길이 ≤ 100
  • 5 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
    • S : 시작 지점
    • E : 출구
    • L : 레버
    • O : 통로
    • X : 벽
  • 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
  • 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

---

 

입출력 예maps                                                                                                                                                         result

["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]	16
["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"]	-1

 

2. 접근 방식

전형적인 BFS 방식의 문제다. 

 

 다만 문제를 접근하며 시작 -> 레버, 레버 -> 출구로 두번 나눠서 탐색을 해야하는데, "아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다." 이 문장을 레버를 당기지 않아도 출구로 나갈 수 있다고 착각해서 헤맸다.

 

 두 번째로 주의할 점은 시작->레버, 레버->출구의 길이 겹치는 경우가 있기 때문에 방문배열 또는 미로 배열을 초기화 해줘야 한다. 

 

3. 구현

import java.util.*;

class Solution {
    static int[][] miro;
    static int[][] tempMiro;
    static Node ent;
    static Node exit;
    static Node lever;
    static int[] ax = {1,-1,0,0};
    static int[] ay = {0,0,1,-1};
    
    static class Node {
        int x,y;
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public int solution(String[] maps) {
        int answer = 0;
        miro = new int[maps.length][maps[0].length()];
        tempMiro = new int[maps.length][maps[0].length()];
        for (int i=0; i<miro.length; i++) {
            String temp = maps[i];
            for (int j=0; j<miro[i].length; j++) {
                if (temp.charAt(j) == 'X') {
                    miro[i][j] = -1;
                    tempMiro[i][j] = -1;
                    continue;
                }
                if (temp.charAt(j) == 'S') {
                    ent = new Node(i, j); 
                }
                if (temp.charAt(j) == 'E') {
                    exit = new Node(i, j);
                }
                if (temp.charAt(j) == 'L') {
                    lever = new Node(i,j);
                }
            }
        }
        bfs(ent, lever);
        if (miro[lever.x][lever.y] == -1) {
            answer = -1;
            return answer;
        }
        answer = miro[lever.x][lever.y];
        miro = tempMiro;
        
        bfs(lever, exit);
        if (miro[exit.x][exit.y] == -1) {
            answer = -1;
            return answer;
        }
        answer += miro[exit.x][exit.y];
        return answer;
    }
    
    public void bfs(Node start, Node end) {
        Queue<Node> q = new LinkedList<Node>();
        q.add(start);
        
        while (!q.isEmpty()) {
            Node now = q.poll();
            for (int i=0; i<4; i++) {
                int nx = ax[i] + now.x;
                int ny = ay[i] + now.y;
                if (nx == end.x && ny == end.y) {
                    miro[nx][ny] = miro[now.x][now.y] + 1;
                    return;
                }
                if (nx >= 0 && ny >= 0 && nx <miro.length && ny<miro[0].length && miro[nx][ny] == 0) {
                    q.add(new Node(nx, ny));
                    miro[nx][ny] = miro[now.x][now.y] + 1;
                }
            }
        }
        miro[end.x][end.y] = -1;
    }
}

 

4. 정리

한동안 문제를 못풀었더니 그새 머리가 굳은것 같다... 꾸준하게 풀자