<프로그래머스> 미로 탈출

<링크>

https://school.programmers.co.kr/learn/courses/30/lessons/159993?language=java

프로그래머스

 

 

<문제>

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

<제한사항>

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

<입력 및 출력>

 

<아이디어>

1. 현재 지점에서 레버까지 갈수 있도록 하나 만들고..

2. 만약 레버까지 못가면 실패 그자체.

3. 만약에, S , E, L 이렇게 있으면... S -> L -> E 형식으로 가야하니까 이부분도 조절하기! (이게.. 테케 23번이더라구요... 이거 때문에 고생고생을...)
4. BFS를 두개 만들어야함..!!

<풀이 - Java >

import java.util.ArrayDeque;
import java.util.Queue;

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

    public int solution(String[] maps) {
        int rows = maps.length;
        int cols = maps[0].length();
        int startX = -1, startY = -1;
        int leverX = -1, leverY = -1;
        int exitX = -1, exitY = -1;

        // 시작점, 레버, 출구의 위치 찾기
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                char c = maps[i].charAt(j);
                if (c == 'S') {
                    startX = i;
                    startY = j;
                } else if (c == 'L') {
                    leverX = i;
                    leverY = j;
                } else if (c == 'E') {
                    exitX = i;
                    exitY = j;
                }
            }
        }

        // 시작점에서 레버까지 가보자잇.
        int toLever = bfs(maps, startX, startY, leverX, leverY);
        // 레버까지 못가면 유감..
        if (toLever == -1) return -1;

        // 레버에서 출구까지 BFS 수행 (출구를 지나면서 시작점을 다시 방문 가능)
        int toExit = bfsStart(maps, leverX, leverY, exitX, exitY, startX, startY);
        // 레버에서 출구까지 못가면 유감...
        if (toExit == -1) return -1;

        return toLever + toExit;
    }

    // BFS 수행, 시작점(S)도 다시 방문할 수 있도록 처리
    private int bfsStart(String[] maps, int startX, int startY, int targetX, int targetY, int initX, int initY) {
        // 행
        int rows = maps.length;
        // 열
        int cols = maps[0].length();
        // 와줘. 제발
        visited = new boolean[rows][cols];
        Queue<int[]> queue = new ArrayDeque<>();
        // 2차원이니까.. int 배열 로 만들어줄꿰
        queue.add(new int[]{startX, startY});
        visited[startX][startY] = true;
        int steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int s = 0; s < size; s++) {
                int[] current = queue.poll();
                int x = current[0];
                int y = current[1];

                // 도착했으면... 그만....
                if (x == targetX && y == targetY) {
                    return steps;
                }

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

                    if (isValid(nx, ny, maps) && !visited[nx][ny]) {
                        char cell = maps[nx].charAt(ny);
                        if (cell == 'L' || cell == 'O' || cell == 'E' 
                        		// 내가 너때문에 고생 고생을... (S -> L -> F로 가게 될경우)
                        		|| (nx == initX && ny == initY)) {
                            visited[nx][ny] = true;
                            queue.add(new int[]{nx, ny});
                        }
                    }
                }
            }
            steps++;
        }

        return -1; // 도착못하면 뭐.. 유감.
    }

    private int bfs(String[] maps, int startX, int startY, int targetX, int targetY) {
        int rows = maps.length;
        int cols = maps[0].length();
        visited = new boolean[rows][cols];
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{startX, startY});
        visited[startX][startY] = true;
        int steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int s = 0; s < size; s++) {
                int[] current = queue.poll();
                int x = current[0];
                int y = current[1];

                if (x == targetX && y == targetY) {
                    return steps;
                }

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

                    if (isValid(nx, ny, maps) && !visited[nx][ny]) {
                        char cell = maps[nx].charAt(ny);
                        if (cell == 'L' || cell == 'O' || cell == 'E') {
                            visited[nx][ny] = true;
                            queue.add(new int[]{nx, ny});
                        }
                    }
                }
            }
            steps++;
        }

        return -1; 
    }

    private boolean isValid(int x, int y, String[] maps) {
        return x >= 0 && x < maps.length && y >= 0 && y < maps[0].length();
    }
}