[프로그래머스] 미로 탈출 (BFS)

https://school.programmers.co.kr/learn/courses/30/lessons/159993?language=java

풀이

---

최단거리 문제 -> BFS 시도
시작 -> 레버 / 레버 -> 도착지

q.add(new int[]{i, j, count});
쓰는 법 알게 되었다.

레버 도착하면 방문 배열, 큐 초기화 시키기

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

class Solution {
    static char[][] graph;
    static int n, m, answer = 0;
    static boolean[][] visited;
    static Queue<int[]> q = new LinkedList<>();
    
    static int[] dx = {-1, 0, 1, 0}; 
    static int[] dy = {0, 1, 0, -1};
    
    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'){
                    q.add(new int[]{i, j, 0});
                    visited[i][j] = true;
                }
            }
        }
        bfs();
    
        return answer;
    }
    public static void bfs() {
        while(!q.isEmpty()){
            int[] temp = q.poll();
            int y = temp[0];
            int x = temp[1];
            int count = temp[2];
            
            // 레버 도착
            if(!lever && graph[y][x] == 'L'){
                // 초기화 해서 레버에서 도착지까지 최단거리
                visited = new boolean[n][m];
                q.clear();
                q.add(new int[]{y, x, count});
                visited[y][x] = true;
                lever = true;
            } else if(lever && graph[y][x] == 'E'){
                answer = count;
                return;
            }
            
            for(int i = 0; i < 4; i++){
                int ny = y + dy[i];
                int nx = x + dx[i];
                if(ny >= 0 && ny < n && nx >= 0 && nx < m){
                    if(!visited[ny][nx] && graph[ny][nx] != 'X'){
                        q.add(new int[]{ny, nx, count+1});
                        visited[ny][nx] =true;
                    }
                        
                }
            }
        }
        answer = -1;
        return;
    }
}코드를 입력하세요

코드 최적화 해보기

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

class Solution {
    static char[][] graph;
    static int n, m, answer = 0;
    static boolean[][] visitedS, visitedL;
    static Queue<int[]> q = new LinkedList<>();
    
    static int[] dx = {-1, 0, 1, 0}; 
    static int[] dy = {0, 1, 0, -1};
    
    public int solution(String[] maps) {
        n = maps.length;
        m = maps[0].length();
        visitedS = new boolean[n][m];
        visitedL = new boolean[n][m];
        graph = new char[n][m];
        
        int leverX = -1, leverY = -1;
        
        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'){
                    q.add(new int[]{i, j, 0});
                    visitedS[i][j] = true;
                } else if (graph[i][j] == 'L') {
                    leverX = i;
                    leverY = j;
                }
            }
        }
        
        // BFS from 'S' to 'L'
        int leverCount = bfs(visitedS, false);
        
        if (leverCount == -1) return -1;
        
        // BFS from 'L' to 'E'
        q.clear();
        q.add(new int[]{leverX, leverY, 0});
        visitedL[leverX][leverY] = true;
        answer = bfs(visitedL, true);
    
        return answer;
    }

    public static int bfs(boolean[][] visited, boolean searchEnd) {
        while(!q.isEmpty()){
            int[] temp = q.poll();
            int y = temp[0];
            int x = temp[1];
            int count = temp[2];
            
            if(!searchEnd && graph[y][x] == 'L'){
                return count;
            } else if(searchEnd && graph[y][x] == 'E'){
                return count;
            }
            
            for(int i = 0; i < 4; i++){
                int ny = y + dy[i];
                int nx = x + dx[i];
                if(ny >= 0 && ny < n && nx >= 0 && nx < m){
                    if(!visited[ny][nx] && graph[ny][nx] != 'X'){
                        q.add(new int[]{ny, nx, count + 1});
                        visited[ny][nx] = true;
                    }
                }
            }
        }
        return -1;
    }
}