[Programmers] 미로 탈출 자바

 

프로그래머스

 

기존코드

---

class Solution {
    //시작 좌표
    private int sx, sy;
    
    //이동 변화값 배열
    private int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    //노드 방문 기록 배열
    private boolean[][] vis;
    
    //최소 시간 기록 변수
    private int answer = Integer.MAX_VALUE;
    
    public void init(String[] maps) {
        for(int i=0; i<maps.length; i++) {
            for(int j=0; j<maps[i].length(); j++) {
                if(maps[i].charAt(j) == 'S') {
                    sx = i;
                    sy = j;
                }
            }
        }
        
        vis = new boolean[maps.length][maps[0].length()];
    }
    
    public int solution(String[] maps) {
        init(maps);
        
        dfs(maps, sx, sy, false, 0);
        
        if(answer == Integer.MAX_VALUE) return -1;
        else return answer;
    }
    
    public void dfs(String[] maps, int x, int y, boolean L, int depth) {
        if(maps[x].charAt(y) == 'E') {            
            //레버를 지났다면
            if(L) answer = Math.min(answer, depth);
            return;
        }
        
        for(int i=0; i<4; i++) {
            //상, 하, 좌, 우 이동
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            
            if(nx >= maps.length || nx < 0 || ny >= maps[0].length() || ny < 0) continue;
            
            char next = maps[nx].charAt(ny);
            if(next == 'X') continue;
            if(vis[nx][ny]) continue;
            
            //다음 좌표가 레버라면
            boolean l = L;
            if(next == 'L') l = !l;
            
            vis[nx][ny] = true;
            dfs(maps, nx, ny, l, depth+1);
            vis[nx][ny] = false;
        }
        
    }
}

 

DFS를 이용해 S에서 L을 지나 E에 도착하는 모든 경우의 수 중 최단 거리를 구하고자 위와 같은 코드를 작성했다. E를 지나 L로 가는 경우의 수가 있기때문에 BFS로 풀 수 없다고 생각했고 멍청하게 DFS로 풀기 시작했다. 당연히 결과는 아래와 같은 실패 폭탄과 무수한 TLE가 발생했다. 탐색을 한 번의 알고리즘으로 돌린다는 생각이 패착이었고 DFS 또한 BFS의 문제점이 발생한다는 사실을 인지하지 못했다.

 

 

위 코드에서 두 가지 문제를 도출했다. 첫번째로는 BFS와 마찬가지로 vis를 기록하기 때문에 E를 지나 L로 다시 L에서 E로가는 경우를 고려하지 못한다. 실패가 나오는 케이스라고 생각했다. 두번째로는 maps 범위의 최댓값이 100*100이다. worst case가 대충 4^10_000 인데 애초에 DFS로 풀려고 접근했던 것 자체가 말도 안된다.

 

 

변경코드

---

BFS를 두 번 돌리는 방식으로 문제를 해결할 수 있었다. S에서 L까지 1번, L에서 E까지 1번 해당 방식을 이용할 경우 첫 번째 문제점을 해결할 수 있었다. 또한, 최단거리를 구하는 문제이기 때문에 BFS에서 이전 노드를 재방문할 필요가 없다. BFS가 한 번 돌때 방문 노드의 수가 maps의 크기의 최대 크기(100*100)를 초과하지 않는다.

import java.util.*;

class Solution {
    //map 크기
    private int N, M;
    
    //시작 좌표, 레버 좌표, 출구 좌표
    private int sx, sy, lx, ly, ex, ey;
    
    //이동 변화값 배열
    private int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    //노드 방문 기록 배열
    private boolean[][] vis;
    
    public void init(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') {
                    sx = i;
                    sy = j;
                }
                if(maps[i].charAt(j) == 'L') {
                    lx = i;
                    ly = j;
                }
                if(maps[i].charAt(j) == 'E') {
                    ex = i;
                    ey = j;
                }
            }
        }
        
        vis = new boolean[N][M];
    }
    
    public int solution(String[] maps) {
        init(maps);
        
        int[] s = {sx, sy};
        int[] l = {lx, ly};
        int[] e = {ex, ey};
        
        int stol = bfs(maps, s, l);
        if(stol == -1) return -1;
        
        //방문 기록 초기화
        for(boolean[] v : vis) {
            Arrays.fill(v, false);
        }
        
        int ltoe = bfs(maps, l, e);
        if(ltoe == -1) return -1;
        
        return stol + ltoe;
    }
    
    public int bfs(String[] maps, int[] start, int[] end) {
        Deque<int[]> dq = new ArrayDeque<>();
        dq.offer(start);
        
        int[][][] hist = new int[N][M][2];
        
        while(!dq.isEmpty()) {
            int[] cur = dq.poll();
            
            if(cur[0] == end[0] && cur[1] == end[1]) {
                int curX = cur[0];
                int curY = cur[1];
                
                int count = 0;
                while(curX != start[0] || curY != start[1]) {                    
                    int[] h = hist[curX][curY];
                    
                    curX = h[0];
                    curY = h[1];
                    
                    count++;
                }
                
                return count;
            }
            
            for(int i=0; i<4; i++) {
                int nx = cur[0] + dir[i][0];
                int ny = cur[1] + dir[i][1];
                
                if(nx >= N || nx < 0 || ny >= M || ny < 0) continue;
                if(maps[nx].charAt(ny) == 'X') continue;
                if(vis[nx][ny]) continue;
                
                vis[nx][ny] = true;
                hist[nx][ny][0] = cur[0];
                hist[nx][ny][1] = cur[1];
                
                int[] next = {nx, ny};
                dq.offer(next);
            }
        }
        
        return -1;
    }
}