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

https://school.programmers.co.kr/learn/courses/30/lessons/159993

프로그래머스

 

 

시작, 레버, 출구는 모두 랜덤이며 하나씩만 존재한다.

그렇다면 각 세 좌표만 구한다면 bfs로 쉽게 풀 수 있을 것이다.

 

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

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

    public int solution(String[] maps) {
        int answer = 0;
        visited = new boolean[maps.length][maps[0].length()];
        int[][] point = new int[3][2];

        for(int i = 0; i < maps.length; i++) {
            for(int j = 0; j < maps[0].length(); j++) {
                if(maps[i].charAt(j) == 'S') {
                    point[0][0] = i;
                    point[0][1] = j;
                }
                if(maps[i].charAt(j) == 'L') {
                    point[1][0] = i;
                    point[1][1] = j;
                }
                if(maps[i].charAt(j) == 'E') {
                    point[2][0] = i;
                    point[2][1] = j;
                }
                
            }
        }
        int check = 0;
        check = bfs(maps, point[0][0], point[0][1], point[1][0], point[1][1], visited);
        if(check == -1) return -1;
        answer += check;
        visited = new boolean[maps.length][maps[0].length()];
        check = 0;
        check = bfs(maps, point[1][0], point[1][1], point[2][0], point[2][1], visited);
        if(check == -1) return -1;
        answer += check;
        return answer;
    }
    int bfs(String[] maps, int startX, int startY, int endX, int endY, boolean[][] visited) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{startX, startY, 0});
        visited[startX][startY] = true;
        while(!q.isEmpty()) {
            int [] curr = q.poll();
            int currX = curr[0];
            int currY = curr[1];
            int distance = curr[2];
            
            if(currX == endX && currY == endY) return distance;
            for(int i = 0; i < 4; i++) {
                int x = currX + dx[i];
                int y = currY + dy[i];

                if(x >= 0 && x < visited.length && y >= 0 && y < visited[0].length 
                && !visited[x][y] && maps[x].charAt(y) != 'X') {
                    visited[x][y] = true;
                    q.offer(new int []{x, y , distance + 1});
                }
            }
        }

        return -1;
    }
}