링크

문제링크

문제

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

해결

bfs를 시작지점에서 레버까지, 레버에서 출구까지 두 번 사용하여 해결하였다.

findNode() 를 통해 시작,레버, 출구 위치 정보를 찾아서 기록한다.

그리고 시작지점에서 레버까지 bfs를 사용한다.

bfs는
queue에 startNode 를 넣고 queue가 비워질때까지 반복한다.
queue에서 다음 Node를 꺼내어 curNode를 초기화 해준다.
curNode가 goalNode 위치인지 확인하고 맞다면 time을 갱신하고 반복을 종료한다.
아니라면 curNode기준으로 상하좌우 위치를 갈수 있는곳인지, 처음 방문하는 곳인지 확인하고 queue에 넣어주고 다음 반복을 한다.

시작지점에서 레버까지 bfs의 반환값이 0이 아니라면 레버에서 출구까지 bfs를 수행한다.
만약 goalNode.time 이 0 이라면 출구까지 도달하지 못하였기에 answer를 -1로 해준다.

코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    
    static class Node {
        int row;
        int col;
        int time;

        public void init(int row, int col) {
            this.row = row;
            this.col = col;
            this.time = 0;
        }

        public Node() {
        }

        public Node(int row, int col, int time) {
            this.row = row;
            this.col = col;
            this.time = time;
        }
    }
    
    public int solution(String[] maps) {
        int answer = 0;

        Node startNode = new Node();
        Node leverNode = new Node();
        Node goalNode = new Node();

        findNode(maps, startNode, leverNode, goalNode);
        bfs(maps, startNode, leverNode);
        if (leverNode.time != 0) {
            bfs(maps, leverNode, goalNode);
        }

        answer = goalNode.time == 0 ? -1 : goalNode.time;
        
        return answer;
    }

    private static void findNode(String[] maps, Node startNode, Node leverNode, Node goalNode) {
        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps[i].length(); j++) {
                if (maps[i].charAt(j) == 'S') {
                    startNode.init(i, j);
                } else if (maps[i].charAt(j) == 'L') {
                    leverNode.init(i, j);
                } else if (maps[i].charAt(j) == 'E') {
                    goalNode.init(i, j);
                }
            }
        }
    }

    public static int bfs(String[] maps, Node startNode, Node goalNode) {
        int maxRow = maps.length;
        int maxCol = maps[0].length();
        boolean[][] visited = new boolean[maxRow][maxCol];
        Queue<Node> queue = new LinkedList<>();
        queue.add(startNode);
        visited[startNode.row][startNode.col] = true;
        
        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            
            // 목표지점이라면 중단
            if (curNode.row == goalNode.row && curNode.col == goalNode.col) {
                goalNode.time = curNode.time;
                break;
            }

            // 상하좌우 방문 , 벽이 아닌곳, 방문하지 않은곳이어야함
            if (curNode.row - 1 >= 0 && maps[curNode.row - 1].charAt(curNode.col) != 'X' && !visited[curNode.row - 1][curNode.col]) {
                visited[curNode.row - 1][curNode.col] = true;
                queue.add(new Node(curNode.row - 1, curNode.col, curNode.time + 1));
            }
            if (curNode.row + 1 < maxRow && maps[curNode.row + 1].charAt(curNode.col) != 'X' && !visited[curNode.row + 1][curNode.col]) {
                visited[curNode.row + 1][curNode.col] = true;
                queue.add(new Node(curNode.row + 1, curNode.col, curNode.time + 1));
            }
            if (curNode.col - 1 >= 0 && maps[curNode.row].charAt(curNode.col - 1) != 'X' && !visited[curNode.row][curNode.col - 1]) {
                visited[curNode.row][curNode.col - 1] = true;
                queue.add(new Node(curNode.row, curNode.col - 1, curNode.time + 1));
            }
            if (curNode.col + 1 < maxCol && maps[curNode.row].charAt(curNode.col + 1) != 'X' && !visited[curNode.row][curNode.col + 1]) {
                visited[curNode.row][curNode.col + 1] = true;
                queue.add(new Node(curNode.row, curNode.col + 1, curNode.time + 1));
            }
        }

        return goalNode.time;
    }

}