미로 탈출

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

프로그래머스

 

전형적으로 bfs를 이용한 최소 경로구하기인데, 디테일을 놓쳐서 고생했다.

바로, bfs에서 if(mapp[nx][ny]!='X') 부분인데,

1)nx,ny의 범위와 vistied체크를 하지 않고 먼저 체크해서 exception이 터졌고,

2)mapp[nx][ny]=='o'으로 했다가 end값과 일치했을 때 return문으로 가지 못했다. 그 이유를 보니, end와 lever는 o가 아닌 다른 문자열로 되어있기 떄문에, mapp[nx][ny]!='X'의 조건을 주어야한다. 

이런 디테일한 부분을 놓치지 말자. 

 

비슷한 문제(?)로는 백준의 공주님 구하기와 비슷한것같다. 

import java.util.*;

class Solution {
    static char[][] mapp;
    static int n, m;
    static int[] dy = new int[] {-1,0,1,0};
    static int[] dx = new int[] {0,-1,0,1};
    
    public int solution(String[] maps) {
        n = maps.length;
        m = maps[0].length();
        mapp= new char[n][m];
        int sx=0, sy=0, lx=0,ly=0, ex=0, ey=0;
        
        for (int i=0; i<maps.length; i++) {
            String temp = maps[i];
            for (int j=0; j<temp.length(); j++) {
                mapp[i][j]=maps[i].charAt(j);
                if (mapp[i][j]=='S') {
                    sx = i;
                    sy = j;
                }
                if (mapp[i][j]=='L') {
                    lx = i;
                    ly = j;
                }
                if (mapp[i][j]=='E') {
                    ex = i;
                    ey = j;
                }
            }
        }
        int to_leve = door(sx, sy, lx, ly);
        if (to_leve ==-1) return -1;
        int to_exit = door(lx, ly, ex, ey);
        if (to_exit ==-1) return -1;
        
        return to_leve+to_exit;
    }
    
    public static int door(int start_x, int start_y, int end_x, int end_y) {
        Queue<int[]> q = new LinkedList<>();
        boolean [][] visited = new boolean[n][m];
        int [] arr = new int[] {start_x, start_y, 0}; //좌표값 저장
        
        q.add(arr);
        visited[start_x][start_y]=true;
        
        while (!q.isEmpty()) {
            int[] tp = q.poll();
            int tp_x = tp[0];
            int tp_y = tp[1];
            int count = tp[2];
            visited[tp_x][tp_y]=true;
            
            if (tp_x==end_x && tp_y==end_y) {
                return count;
            }
            
            for (int k=0; k<4; k++) {
                int nx = tp_x+dx[k];
                int ny = tp_y + dy[k];
                    if (0<=nx && nx<n && 0<=ny && ny<m && !visited[nx][ny]) {
                        if (mapp[nx][ny]!='X') { //디테일 1: 먼저 범위체크부터!, 디테일 2: s와 l로 도달하려면 =='o'이 아닌 !=x로 체크해야함
                            q.add(new int[] {nx,ny,count+1});
                            visited[nx][ny]=true;
                    }   
                }
            }
        }
        return -1;
    }
    
    
}