[프로그래머스] 미로 탈출

문제

미로의 출구를 찾아 최단 경로로 탈출하는데, 중간에 레버를 당기고 탈출해야하는 문제이다.

---

풀이방법

풀이 시간 : 20분

풀이 방법 : BFS

 

BFS를 이용해 최단 경로를 만들어주면 되는데 레버를 당기는게 이 문제의 핵심이다.

쉽게는 그냥 시작점 -> 레버 + 레버 + 탈출구의 경로를 찾아 더해주면 된다.

---

코드

import java.io.*;
import java.util.*;

class Solution {
    static final int[] dx = {1, -1, 0, 0};
    static final int[] dy = {0, 0, -1, 1};

    static int n, m;
    static char[][] map;

    public int solution(String[] maps) {
        n = maps.length;
        m = maps[0].length();
        map = new char[n][m];

        Road start = null, lever = null, exit = null;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char ch = maps[i].charAt(j);
                map[i][j] = ch;
                if (ch == 'S') start = new Road(i, j);
                else if (ch == 'L') lever = new Road(i, j);
                else if (ch == 'E') exit = new Road(i, j);
            }
        }

        int toLever = bfs(start, lever);
        if (toLever == -1) return -1;

        int toExit = bfs(lever, exit);
        if (toExit == -1) return -1;

        return toLever + toExit;
    }

    private int bfs(Road start, Road target) {
        boolean[][] visited = new boolean[n][m];
        Queue<Road> q = new LinkedList<>();
        q.offer(start);
        visited[start.x][start.y] = true;

        while (!q.isEmpty()) {
            Road cur = q.poll();

            if (cur.x == target.x && cur.y == target.y) return cur.depth;

            for (int d = 0; d < 4; d++) {
                int nx = cur.x + dx[d];
                int ny = cur.y + dy[d];

                if (!inRange(nx, ny) || map[nx][ny] == 'X' || visited[nx][ny]) continue;

                visited[nx][ny] = true;
                q.offer(new Road(nx, ny, cur.depth + 1));
            }
        }

        return -1;
    }

    private boolean inRange(int x, int y) {
        return x >= 0 && y >= 0 && x < n && y < m;
    }

    private static class Road {
        int x, y, depth;

        Road(int x, int y) {
            this(x, y, 0);
        }

        Road(int x, int y, int depth) {
            this.x = x;
            this.y = y;
            this.depth = depth;
        }
    }
}