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

링크

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

프로그래머스

 

설명

미로에서 레버를 통과한 후 결과지점을 찾는 문제이다.

BFS를 2번 하였다.

1번 BFS : 시작점에서 레버까지 도달하는 거리 찾기
2번 BFS : 레버부터 도착점까지 도달하는 거리 찾기

 

각 BFS에서 찾지 못하는 경우 -1 을 반환 (목표지점까지 찾기가 막혔다는 뜻)

찾은 경우 각 단계에서 찾은 최소 거리를 각각 다해서 반환한다.

 

 

풀이

import java.util.*;

class Solution {
    // 상, 하, 좌, 우
    int[] dx = new int[]{0, 0, -1, 1};
    int[] dy = new int[]{-1, 1, 0, 0};
    public int solution(String[] maps) {
        int r = maps.length;
        int c = maps[0].length();
        String[][] cells = new String[r][c];
        // start
        int sx = 0;
        int sy = 0;
        // lever
        int lx = 0;
        int ly = 0;
        // goal
        int gx = 0;
        int gy = 0;
        for (int i=0; i<r; i++) {
            String[] mapLine = maps[i].split("");
            for(int j=0; j<c; j++) {
                String cell = mapLine[j];
                cells[i][j] = cell;
                if (cell.equals("S")) {
                    sx = i;
                    sy = j;
                }
                
                if (cell.equals("L")) {
                    lx = i;
                    ly = j;
                }
                
                if (cell.equals("E")) {
                    gx = i;
                    gy = j;
                }
            }
        }
        
        // totalStepCount
        int totalStepCount = 0;
        // find path lever
        boolean[][] visitedLeverPath = new boolean[r][c];
        Queue<int[]> lq = new LinkedList<>();
        lq.add(new int[]{sx, sy, 0});
        visitedLeverPath[sx][sy] = true;
        
        boolean visitedlever = false;
        while(!lq.isEmpty()) {
            int[] point = lq.poll();
            int cx = point[0];
            int cy = point[1];
            int count = point[2];
            if (cells[cx][cy].equals("L")) {
                visitedlever = true;
                totalStepCount += count;
                break;
            }
            
            for (int i=0; i<4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                
                if (nx >= 0 && nx < r && ny >=0 && ny < c) {
                    if (visitedLeverPath[nx][ny]) {
                        continue;
                    }
                    
                    if (cells[nx][ny].equals("X")) {
                        continue;
                    }
                    
                    visitedLeverPath[nx][ny] = true;
                    lq.add(new int[]{nx, ny, count + 1});
                }
            }
        }
        
        // 레버 찾기 실패 경우
        if (!visitedlever) {
            return -1;
        }
        
        // 레버는 찾았다면 골까지 ㄱㄱ
        boolean[][] visitedGoalPath = new boolean[r][c];
        Queue<int[]> gq = new LinkedList<>();
        gq.add(new int[]{lx, ly, 0});
        visitedGoalPath[lx][ly] = true;
        boolean visitedGoal = false;
        while(!gq.isEmpty()) {
            int[] point = gq.poll();
            int cx = point[0];
            int cy = point[1];
            int count = point[2];
            if (cells[cx][cy].equals("E")) {
                visitedGoal = true;
                totalStepCount += count;
                break;
            }
            
            for (int i=0; i<4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                
                if (nx >= 0 && nx < r && ny >=0 && ny < c) {
                    if (visitedGoalPath[nx][ny]) {
                        continue;
                    }
                    
                    if (cells[nx][ny].equals("X")) {
                        continue;
                    }
                    
                    visitedGoalPath[nx][ny] = true;
                    gq.add(new int[]{nx, ny, count + 1});
                }
            }
        }
        
        if (!visitedGoal) {
            return -1;
        }
        
        return totalStepCount;
    }
}