프로그래머스 미로탈출 java

문제링크

문제 접근

• 시작지점 -> 레버 bfs, 레버 -> 종료지점 bfs 두번 실행
• 각각 실행했을 때 찾지 못하면 -1 리턴
• 이동 횟수는 공유

코드

import java.util.*;
class Solution {
    static int N,M;
    static point S,E,L;
    static int answer;
    static boolean isLever = false;
    static boolean isExit = false;
    static int[] di = {1,-1,0,0};
    static int[] dj = {0,0,1,-1};
    public int solution(String[] maps) {
        N = maps.length;
        M = maps[0].length();
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(maps[i].charAt(j) == 'S') S = new point(i,j);
                else if(maps[i].charAt(j) == 'E') E = new point(i,j);
                else if(maps[i].charAt(j) == 'L') L = new point(i,j);
            }
        }
        bfs('L', maps);
        if(isLever){
            bfs('E', maps);
        }
        else{
            return -1;
        }
        if(!isExit) return -1;
        return answer;
    }
    private static void bfs(char Type, String[] maps){
        Queue<point> que = new LinkedList<>();
        boolean[][] visit = new boolean[N][M];
        if(Type == 'L') {
            que.add(new point(S.i, S.j));
            visit[S.i][S.j] = true;
        }
        else if(Type == 'E') {
            que.add(new point(L.i, L.j));
            visit[L.i][L.j] = true; 
        }
        
        while(!que.isEmpty()){
            int size = que.size();
            for(int s=0;s<size;s++){
                point now = que.poll();
                for(int d=0;d<4;d++){
                    int nexti = now.i + di[d];
                    int nextj = now.j + dj[d];
                    if(nexti<0 || nexti>=N || nextj<0 || nextj>=M) continue;
                    if(visit[nexti][nextj] || maps[nexti].charAt(nextj) == 'X') continue;    
                    if(maps[nexti].charAt(nextj) == 'O' || maps[nexti].charAt(nextj) == 'S'){
                        que.add(new point(nexti, nextj));
                        visit[nexti][nextj] = true;
                    }
                    else if(maps[nexti].charAt(nextj) == 'L'){
                        if(Type == 'L'){
                            answer++;
                            isLever = true;
                            return;
                        }
                        else{
                            que.add(new point(nexti, nextj));
                            visit[nexti][nextj] = true;
                        }
                    }
                    else if(maps[nexti].charAt(nextj) == 'E'){
                        if(Type == 'E'){
                            answer++;
                            isExit = true;
                            return;
                        }
                        else{
                            que.add(new point(nexti, nextj));
                            visit[nexti][nextj] = true;
                        }
                    }
                }
            }
            answer++;
        }
    }
    private static class point{
        int i;
        int j;
        public point(int i, int j){
            this.i = i;
            this.j = j;
        }
    }
}

결과

정리

• 레버로 이동할 때 도착 지점도 통과 가능