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

문제 파악

-시작점에서 도착지점까지 한 칸씩 이동하며 카운트하기

-레버 만나야 도착지점으로 갈 수 있음

• 5 ≤ maps의 길이 ≤ 100
  • 5 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
    • S : 시작 지점
    • E : 출구
    • L : 레버
    • O : 통로
    • X : 벽
  • 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
  • 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

 

 

접근 방법

-시작점 S가 어디에 있는지 먼저 찾아서 거기서부터 각 방향으로 갈 수 있는지 유효성 검사(isValid)

-갈 수 있는 방향 따라 가면서 큐에 가능한 경로 좌표 담기

-bfs를 활용해 도착지점까지 최소거리 구하기(큐에 담을 때는 x,y좌표와 한칸씩 이동하면서 카운트 세기)

-좌표 담기 전 유효성 검사와 방문 여부 검사하고, 통과하면 큐에 담기

-목적지 가는 도중 레버를 들려야 하므로, 레버까지의 bfs를 구해 카운트 변수에 따로 빼주고,

-레버에서 목적지까지 bfs를 구해 위의 레버까지의 최소거리와 더한다. ⇒ 결과값 리턴

-만일 도착 지점 혹은 출발 지점에 X가 가로막혀있거나,

레버를 찾을 수 없어 도착지점에 도달할 수 없다면 -1리턴

 

코드 구현

import java.util.*;
class Solution {
    public int solution(String[] maps) {
        int n=maps.length;
        int m=maps[0].length();
        Queue<int[]> que=new ArrayDeque<>();
        boolean[][] visited = new boolean[n][m];
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                char c=maps[i].charAt(j);
                if(c=='S'){//시작점
                    if(isValid(i,j,maps) && !visited[i][j]){
                        que.offer(new int[]{i,j,0});
                        visited[i][j]=true;
                    }
                }
            }
        }
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        int lx=0;int ly=0;int findl=0;
        while(!que.isEmpty()){
            int[] node = que.poll();
            int cx = node[0];
            int cy = node[1];
            int cnt = node[2];
            if (maps[cx].charAt(cy) == 'L') {
                lx=cx;
                ly=cy;
                findl=cnt;
                break;
            }
            for (int i = 0; i < 4; i++) {
                int x = cx + dx[i];
                int y = cy + dy[i];
                if(isValid(x,y,maps) && !visited[x][y]){
                    que.offer(new int[]{x,y,cnt+1});
                    visited[x][y]=true;
                }
            }
        }
        if(findl==0) return -1;
        que.clear();
        visited=new boolean[n][m];
        que.offer(new int[]{lx, ly, 0});
        visited[lx][ly] = true;//레버부터 시작

        while(!que.isEmpty()){
            int[] node = que.poll();
            int cx = node[0];
            int cy = node[1];
            int cnt = node[2];
            
            for (int i = 0; i < 4; i++) {
                int x = cx + dx[i];
                int y = cy + dy[i];
                if(isValid(x,y,maps) && !visited[x][y]){
                    if (maps[x].charAt(y) == 'E') {
                        return cnt +=findl+1;
                    }
                    que.offer(new int[]{x,y,cnt+1});
                    visited[x][y]=true;
                }
            }
        }
        return -1;
    }
    public boolean isValid(int x,int y,String[] maps){
        if(x<0 || x>=maps.length || y<0 || y>=maps[0].length() || maps[x].charAt(y) == 'X'){
            return false;
        }
        return true;
    }
}

배우게 된 점

-출발-도착으로의 최소 거리만 구해봐서 레버가 무엇을 의미하는지 몰랐는데,

제출하니 오류가 나서 문제를 다시 보니 레버가 결과까지 가기에 중요한 역할을 했다.

-즉, 레버를 꼭 방문해야만 하는 것. 레버를 방문하고 레버를 기점으로 목적지까지 가야하니

각 경로를 두개로 나누어 최소거리를 구한다. 그리고 두개를 더해야 정답 완성

-isValid함수 작성 시, 범위 설정에 주의하자.