프로그래머스 Lv2 미로 탈출

나는 처음에 레버와의 거리도 생각하면서 복잡하게 풀라고 했는데 bfs라는 문제의 기본 틀을 구글링 하면서 다른 사람들의 풀이를 보고 그렇게까지 복잡하게 생각을 안해도 된다는 것을 알 수 있었다.

먼저 내 코드는

import java.util.*;

class Solution {
    public static char[][] arr;
    public static int leverX;
    public static int leverY;
    public static int startX;
    public static int startY;
    public static int endX;
    public static int endY;
    public static int[] dy = {-1,1,0,0};
    public static int[] dx = {0,0,-1,1};
    public static boolean[][] visited;
    public int solution(String[] maps) {
        leverX = 0;
        leverY = 0;
        startX = 0;
        startY = 0;
        endX = 0; 
        endY = 0;
        visited = new boolean[maps.length][maps[0].length()];
        arr =new char[maps.length][maps[0].length()];
        
        //0. 이차원 배열 만들기
        for (int i = 0; i < maps.length; i++) {
            String temp = maps[i];
            for (int j = 0; j < temp.length(); j++) {
                arr[i][j] = temp.charAt(j);
                if (arr[i][j] == 'L') {
                    leverX = j;
                    leverY = i;
                } else if (arr[i][j] == 'S') {
                    startX = j;
                    startY = i;
                } else if (arr[i][j] == 'E') {
                    endX = j;
                    endY = i;
                }
            }
        }
        
        //1. lever 찾기
        int first = leverBfs();
        if(first == -1) {
            return -1;
        }
        
        //2.end찾기
        visited = new boolean[maps.length][maps[0].length()];
        int last = bfs();
        if(last == -1) {
            return -1;
        }
        
        
        int answer = first + last;
        return answer;
    }
    public static int leverBfs() {        

        
        while () {
            int[] temp = queue.poll();
            int currentY = temp[0];
            int currentX = temp[1];
            int cnt = temp[2];
            
           for (int i = 0; i < 4; i++) {
               int newDx = dx[i] + currentX;
               int newDy = dy[i] + currentY;
               
               if (newDx < arr[0].length && newDy < arr.length && newDy >= 0 && newDx >= 0) {
                
               }
               
               
           }
        }
        return -1;
        
    }
       public static int bfs() {        

        
        while () {
            int[] temp = queue.poll();
            int currentY = temp[0];
            int currentX = temp[1];
            int cnt = temp[2];
            
           for (int i = 0; i < 4; i++) {
               int newDx = dx[i] + currentX;
               int newDy = dy[i] + currentY;
               
               if (newDx < arr[0].length && newDy < arr.length && newDy >= 0 && newDx >= 0) {
                
               }
               
               
           }
        }
        return -1;
        
    }

}

 

딱 이런 상태였다

뭔가 기억이 날락말락해가지구 힌트를 봐서 bfs의 정석 틀대로 풀었다.

bfs/dfs 틀을 어느정도 기억하면 이 문제처럼 아무리 복잡해도 풀 수 있다!! 

제발 복습해서 내껄루 익히자 ㅎㅎ

 

정답

import java.util.*;

class Solution {
    public static char[][] arr;
    public static int leverX;
    public static int leverY;
    public static int startX;
    public static int startY;
    public static int endX;
    public static int endY;
    public static int[] dy = {-1,1,0,0};
    public static int[] dx = {0,0,-1,1};
    public static boolean[][] visited;
    public int solution(String[] maps) {
        leverX = 0;
        leverY = 0;
        startX = 0;
        startY = 0;
        endX = 0; 
        endY = 0;
        visited = new boolean[maps.length][maps[0].length()];
        arr =new char[maps.length][maps[0].length()];
        
        //0. 이차원 배열 만들기
        for (int i = 0; i < maps.length; i++) {
            String temp = maps[i];
            for (int j = 0; j < temp.length(); j++) {
                arr[i][j] = temp.charAt(j);
                if (arr[i][j] == 'L') {
                    leverX = j;
                    leverY = i;
                } else if (arr[i][j] == 'S') {
                    startX = j;
                    startY = i;
                } else if (arr[i][j] == 'E') {
                    endX = j;
                    endY = i;
                }
            }
        }
        
        //1. lever 찾기
        int first = leverBfs();
        if(first == -1) {
            return -1;
        }
        
        //2.end찾기
        visited = new boolean[maps.length][maps[0].length()];
        int last = bfs();
        if(last == -1) {
            return -1;
        }
        
        
        int answer = first + last;
        return answer;
    }
    public static int leverBfs() {        
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{startY, startX, 0});
        visited[startY][startX] = true;
        
        
        while (!queue.isEmpty()) {
            int[] temp = queue.poll();
            int currentY = temp[0];
            int currentX = temp[1];
            int cnt = temp[2];
            
           for (int i = 0; i < 4; i++) {
               int newDx = dx[i] + currentX;
               int newDy = dy[i] + currentY;
               
               if (newDx < arr[0].length && newDy < arr.length && newDy >= 0 && newDx >= 0) {
                   if (arr[newDy][newDx]=='L') {
                       leverX = newDx;
                       leverY = newDy;
                       return cnt + 1;
                   }
                    if(!(arr[newDy][newDx] == 'X') && !visited[newDy][newDx]) {
                        visited[newDy][newDx] = true;
                        queue.add(new int[]{newDy, newDx, cnt + 1});
                    }
               }
               
               
           }
        }
        return -1;
        
    }
       public static int bfs() {        
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{leverY, leverX, 0});
        visited[leverY][leverX] = true;
        
        
        while (!queue.isEmpty()) {
            int[] temp = queue.poll();
            int currentY = temp[0];
            int currentX = temp[1];
            int cnt = temp[2];
            
           for (int i = 0; i < 4; i++) {
               int newDx = dx[i] + currentX;
               int newDy = dy[i] + currentY;
               
               if (newDx < arr[0].length && newDy < arr.length && newDy >= 0 && newDx >= 0) {
                   if (arr[newDy][newDx]=='E') {
                       endX = newDx;
                       endY = newDy;
                       return cnt + 1;
                   }
                    if(!(arr[newDy][newDx] == 'X') && !visited[newDy][newDx]) {
                        visited[newDy][newDx] = true;
                        queue.add(new int[]{newDy, newDx, cnt + 1});
                    }
               }
               
               
           }
        }
        return -1;
        
    }

}