[프로그래머스] 미로 탈출 Java

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

프로그래머스

입력

문자열 배열 maps는 미로의 정보를 담고 있으며 각 문자는 한 칸을 의미
'S'는 시작점, 'L'은 레버, 'E'는 도착점, 'O'는 빈칸, 'X'는 벽을 의미

 

핵심 아이디어

미로에서 S → L → E 순서로 이동할 수 있는 최단 경로를 각각의 BFS로 계산
시작점에서 레버까지, 레버에서 도착점까지 두 번의 경로 탐색 수행
각 경로가 존재하지 않으면 -1을 반환
두 경로가 모두 존재하는 경우 각각의 거리 합에 시작점과 레버, 레버와 도착점 간 이동을 포함해 총 거리 계산

 

변수설명

dx, dy는 4방향 이동을 위한 좌표 변화량
map은 문자열 배열 maps를 2차원 문자열 배열로 변환한 맵 정보
start, lever, end는 각각 S, L, E의 좌표를 담은 정수 배열
q는 BFS에 사용되는 탐색 큐
distance는 방문 여부 및 이동 거리를 기록하는 2차원 정수 배열
curX, curY는 현재 탐색 중인 좌표
newX, newY는 이동 후 좌표

 

예시

maps가 ["SOO", "OXL", "OEO"]인 경우
S에서 L까지의 최단 거리 2
L에서 E까지의 최단 거리 2
총 경로는 존재하며 이동 횟수는 2 + 2 + 2 = 6
결과는 6

 

정답코드

import java.util.*;

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

    public int solution(String[] maps) {
        int answer = 0;

        String[][] map = new String[maps.length][maps[0].length()];

        int[] start = new int[2];
        int[] lever = new int[2];
        int[] end = new int[2];

        // String[] 배열을 map으로
        for(int i=0; i<maps.length;i++){
            for (int j = 0; j < maps[i].length(); j++) {
                char ch = maps[i].charAt(j);
                if(ch == 'S'){
                    map[i][j] = "S";
                    start[0] = i;
                    start[1] = j;
                } else if(ch == 'L'){
                    map[i][j] = "L";
                    lever[0] = i;
                    lever[1] = j;
                } else if(ch == 'E'){
                    map[i][j] = "E";
                    end[0] = i;
                    end[1] = j;
                }
                else if(ch == 'X')
                    map[i][j] = "X";
                else if(ch == 'O')
                    map[i][j] = "O";
            }
        }

        int a = bfs(map, start, lever);
        int b = bfs(map, lever, end);

        if(a != -1 && b != -1)
            return a+b+2;
        else return -1;

    }


    public int bfs(String[][] map, int[] start, int[] end){

        int n = map.length;
        int m = map[0].length;

        // bfs 사용을 위한 큐
        Queue<int[]> q = new LinkedList<>();

        // 방문 노드 체크
        int[][] distance = new int[map.length][map[0].length];
        for(int[] v : distance)
            Arrays.fill(v, -1);

        int curX = start[0];
        int curY = start[1];

        // q에 시작값 삽입
        q.add(new int[]{curX, curY});

        // 반복
        while(!q.isEmpty()){
            System.out.println(q.size());
            int[] now = q.poll();
            curX = now[0];
            curY = now[1];

            // 목적지 도착
            if (curX == end[0] && curY == end[1]) {
                return distance[curX][curY];
            }

            // 4방향 탐색
            for(int i=0; i<4; i++){
                int newX = curX+dx[i];
                int newY = curY+dy[i];

                // 미로 범위 바깥일 경우, 이미 방문한경우, 벽인경우 >> 무시
                if (newX < 0 || newX >= n || newY < 0 || newY >= m || distance[newX][newY] > 0 || map[newX][newY].equals("X")) {
                    continue;
                }

                // 방문횟수 + 1
                distance[newX][newY] = distance[curX][curY] + 1;
                q.add(new int[]{newX, newY});
            }
        }

        // 목적지까지 경로 없는경우 -1 return
        return -1;
    }

}