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

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

프로그래머스

 

[난이도]

- level 2

 

[알고리즘]

- BFS

 

[코드]

import java.util.*;
import java.io.*;

class Solution {
    static char[][] graph;
    static int n, m, answer = 0;
    static boolean[][] visited;
    static Queue<int[]> queue = new LinkedList<>();
    static int[] dx = {-1, 1, 0, 0}; // 상, 하
    static int[] dy = {0, 0, -1, 1}; // 좌, 우 4방탐색
    static boolean lever = false;
    public int solution(String[] maps) {
        n = maps.length;
        m = maps[0].length();
        visited = new boolean[n][m];
        graph = new char[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                graph[i][j] = maps[i].charAt(j);
                if(graph[i][j] == 'S'){
                    queue.offer(new int[]{i, j, 0});
                    visited[i][j] = true;
                }
            }
        }
        bfs();
    
        return answer;
    }
    static void bfs(){
        while(!queue.isEmpty()){
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            int count = tmp[2];
            if(!lever&&graph[x][y] == 'L') { // 레버에 도착했을 경우, 레버를 아직 안켰을경우
                visited = new boolean[n][m];
                queue.clear();
                queue.offer(new int[]{x, y, count});
                visited[x][y] = true;
                lever = true;
            } else if(lever && graph[x][y] == 'E'){ // 레버를 켠 후 출구에 도착했을 경우
                answer = count;
                return;
            }
            for(int i=0;i<4;i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx>=0&&nx<n&&ny>=0&&ny<m){ // 맵 범위 내에 있을 경우
                    if(!visited[nx][ny] && graph[nx][ny] != 'X'){ // 방문한 적이 없고 벽이 아닐경우
                        queue.offer(new int[]{nx, ny, count+1});
                        visited[nx][ny] = true;
                    }
                }
            }
        }
        answer = -1;
        return;
    }
}

[풀이]

일반적인 BFS와 같지만 두 가지의 조건을 추가했다.

 

레버에 처음 도착했을경우 visited 배열을 다시 초기화해준다. 이유는 레버를 켠 후부터는 방문했던칸을 다시 방문해도 되기 때문이다.

queue를 queue.clear()메서드로 모두 비워준다. 레버에 도착한 순간 큐에담겨있던 데이터들은 쓸모없는 데이터들이기 때문이다.

레버를 켰다는 표시인 lever = true; 해준다.

if(!lever&&graph[x][y] == 'L') { // 레버에 도착했을 경우, 레버를 아직 안켰을경우
                visited = new boolean[n][m];
                queue.clear();
                queue.offer(new int[]{x, y, count});
                visited[x][y] = true;
                lever = true;
            }

 

lever를 켜서 lever = true로 된상태이면서 출구('E')에 도착했을 경우 answer = count; 해준 후 return으로 종료해준다.

else if(lever && graph[x][y] == 'E'){ // 레버를 켠 후 출구에 도착했을 경우
                answer = count;
                return;
            }