[프로그래머스] 미로 탈출 (자바)

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

프로그래머스

---

문제

 

주어진 미로에서 시작점 ( S ) 로 부터 레버 ( L )을 당기고 다시 탈출구 ( E ) 를 도달하는데 최단 거리를 구하는 문제

---

 

풀이

 

최단 거리 이므로 bfs를 이용해서 푼다. 

레버까지의 최단거리 + 레버부터 출구까지의 최단거리 를 하면 정답이 된다. 

 

레버 혹은 출구에 한번이라도 도달하지 못할 시 -1 을 리턴한다. 

 

*주의 미로는 정사각형이 아니다. 

 

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

class Solution {
    static String[][] MIRO;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0 , -1, 1};
    
    public int solution(String[] maps) {
        MIRO = new String[maps.length][maps[0].length()];
        int[] start = new int[2];
        int[] labor = new int[2];
        
        for(int i = 0; i<maps.length; i++) {
            String[] tmp = maps[i].split("");
            
            for(int j = 0; j<tmp.length; j++) {
                MIRO[i][j] = tmp[j];
                
                if (MIRO[i][j].equals("S")) {
                    start = new int[]{i, j};
                }
    
                if (MIRO[i][j].equals("L")) {
                    labor = new int[]{i, j};
                }
            }
        }
        
        int result = bfs(start, "L");
        int result2 = bfs(labor, "E");
        
        if (result == -1 || result2 == -1)
            return -1;
        
        return result + result2;
    }
    
    public int bfs(int[] start, String target) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{start[0], start[1], 0});
        
        boolean[][] visited = new boolean[MIRO.length][MIRO[0].length];
    
        while(!queue.isEmpty()) {
            int x = queue.peek()[0];
            int y = queue.peek()[1];
            int count = queue.peek()[2];
            visited[x][y] = true;
            
            if (MIRO[x][y].equals(target)) {
                return count;
            }
            
            queue.poll();
        
            for(int i = 0; i<4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
            
                if (nx >= 0 && nx < MIRO.length && ny >= 0 && ny < MIRO[0].length && !visited[nx][ny]) {
                    if (!MIRO[nx][ny].equals("X")) {
                        visited[nx][ny] = true;
                        queue.add(new int[]{nx, ny, count+1});
                    }
                }
            }
        }
        
        return -1;
    }
}