(Java) 프로그래머스 - 미로 탈출

오랜만에 푸는 BFS 문제였다.

기본적인 BFS 문제에서 약간 더 생각을 해야했는데, 로직을 생각하는데 그리 오래 걸리지는 않았다.

---

로직

먼저, 탈출을 하기 위해서는 레버까지 가야한다.

그렇기 때문에 레버까지 BFS를 통해 최단거리 탐색을 진행한다.

레버에 도착하고 다시 한번 탈출지점까지 BFS 탐색을 하는데, 여기서 중요한것은 왔던길을 다시 갈 수도 있다는 것이다.

따라서 방문 배열을 초기화 하고 BFS 탐색을 진행해야 한다.

 

탈출 조건이 (시작지점에서 레버에 도달 && 레버에서 탈출지점까지 도달) 이므로 둘중 하나라도

만족하지 못하면 -1을 리턴해야 한다.

 

최종 코드

import java.util.*;

class Solution {

    static int[] dRow = {-1, 1, 0, 0};
    static int[] dCol = {0, 0, -1, 1};
    static int[] lever = new int[2];

    public int solution(String[] maps) {
        int answer = 0;
		
        // 탐색을 위한 2차원 배열과 방문 배열 초기화
        String[][] map = new String[maps.length][maps[0].length()];
        boolean[][] visited = new boolean[maps.length][maps[0].length()];
        int[] start = new int[2];
		
        // 2차원 배열을 만들며 최초 시작 위치 탐색
        for(int i = 0; i < maps.length; i++) {
            String[] temp = maps[i].split("");
            map[i] = temp;
            for(int j = 0; j < temp.length; j++) {
                if(temp[j].equals("S")) {
                    start[0] = i;
                    start[1] = j;
                }
            }
        }
		
        // 레버까지 BFS 탐색
        int first = bfs(map, visited, start, "L");
        if(first == -1) {
            return -1;
        }
		
        // 탈출지점까지 BFS 탐색
        visited = new boolean[maps.length][maps[0].length()];
        int second = bfs(map, visited, lever, "E");
        if(second == -1) {
            return -1;
        }
        
        answer = first + second;
        return answer;
    }

    public int bfs(String[][] map, boolean[][] visited, int[] start, String target) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{start[0], start[1], 0});
        visited[start[0]][start[1]] = true;

        while(!queue.isEmpty()) {
            int[] temp = queue.poll();
            int currentRow = temp[0];
            int currentCol = temp[1];
            int cnt = temp[2];

            for(int i = 0; i < 4; i++) {
                int newRow = currentRow + dRow[i];
                int newCol = currentCol + dCol[i];
                if(newRow >= 0 && newRow < map.length && newCol >= 0 && newCol < map[0].length) {
                    if(map[newRow][newCol].equals(target)) {
                        lever[0] = newRow;
                        lever[1] = newCol;
                        return cnt + 1;
                    }
                    if(!map[newRow][newCol].equals("X") && !visited[newRow][newCol]) {
                        visited[newRow][newCol] = true;
                        queue.add(new int[]{newRow, newCol, cnt + 1});
                    }
                }
            }
        }
        return -1;
    }
}