[Programmers] 미로 탈출

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

프로그래머스

문제 설명

기본적인 BFS 문제이다. 문제는 복잡하지 않으므로 사이트 설명을 확인하기 바란다.

풀이 방법

기본적인 BFS 탐색을 활용하면 된다. BFS의 원리와 구현만 할 수 있다면 충분히 풀 수 있는 문제이다. 이외에 추가적인 알고리즘은 없으므로 코드로 확인하자.

import java.util.*;

class Solution {
    
    static int N, M;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static char[][] charmaps;
    
    public int solution(String[] maps) {
        int answer = 0;
        N = maps.length;
        M = maps[0].length();
        Position start = null;
        
        // 메인 로직을 단순화하기 위해 X로 한 번 감싼다.
        charmaps = new char[N + 2][M + 2];
        wrapWall();
        
        for (int i = 1; i <= N; i++) {
            char[] chars = maps[i - 1].toCharArray();
            for (int j = 1; j <= M; j++) {
                charmaps[i][j] = chars[j - 1];
                if (chars[j - 1] == 'S') start = new Position(i, j, 0);
            }
        }
        
        Position lever = bfs(start, 'L');
        if (lever.time == -1) return -1;
        
        Position exit = bfs(lever, 'E');
        if (exit.time == -1) return -1;
        
        answer = exit.time;
        
        return answer;
    }
    
    private Position bfs(Position p, char target) {
        boolean[][] isVisited = new boolean[N + 2][M + 2];
        Queue<Position> q = new LinkedList<>();
        q.offer(p);
        isVisited[p.x][p.y] = true;
        
        while (!q.isEmpty()) {
            Position curP = q.poll();
            
            if (charmaps[curP.x][curP.y] == target) return curP;
            
            for (int i = 0; i < 4; i++) {
                int nx = curP.x + dx[i];
                int ny = curP.y + dy[i];
                
                if (!isVisited[nx][ny] && charmaps[nx][ny] != 'X') {
                    q.offer(new Position(nx, ny, curP.time + 1));
                    isVisited[nx][ny] = true;
                }
            }
        }
        
        return new Position(1, 1, -1);
    }
    
    private static class Position {
        int x;
        int y;
        int time;
        
        public Position(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }
    
    private void wrapWall() {
        for (int i = 0; i <= N + 1; i++) {
            charmaps[i][0] = 'X';
        }
        
        for (int i = 0; i <= N + 1; i++) {
            charmaps[i][M + 1] = 'X';
        }
        
        for (int i = 0; i <= M + 1; i++) {
            charmaps[0][i] = 'X';
        }
        
        for (int i = 0; i <= M + 1; i++) {
            charmaps[N + 1][i] = 'X';
        }
    }
}