[Programmers] 미로 탈출 / ⭕

프로그래머스

 

1. 제출 코드 (26분 25초 / BFS)

import java.util.*;

class Solution {
    static class Pos {
        int x;
        int y;
        int dist;
        public Pos(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    // 시작, 끝, 레버 위치 저장
    static Pos start, end, lever;
    // 미로 저장
    static ArrayList<Character>[] miro;
    // 방문 배열
    static boolean[][] visited;
    static int row, col;
    
    public int solution(String[] maps) {
        int answer = 0;
        row = maps.length;
        col = maps[0].length();
        miro = new ArrayList[row];
        visited = new boolean[row][col];
        for(int i = 0; i < row; i++) {
            miro[i] = new ArrayList<>();
            for(int j = 0; j < col; j++) {
                char input = maps[i].charAt(j);
                if(input == 'S') {
                    start = new Pos(i, j, 0);
                    visited[i][j] = true;
                } else if (input == 'L') {
                    lever = new Pos(i, j, 0);
                } else if (input == 'E') {
                    end = new Pos(i, j, 0);
                }
                miro[i].add(maps[i].charAt(j));
            }
        }
        // 시작 to 레버까지 거리 계산
        int toLever = bfs(start, lever);
        // 같은 곳을 여러 번 방문할 수 있음
        visited = new boolean[row][col];
        // 레버 to 끝까지 거리 계산
        int toEnd = bfs(lever, end);
        if(toLever == -1 || toEnd == -1) {
            return -1;
        }
        // 합산 거리
        answer = toLever + toEnd;
        return answer;
    }
    static public int bfs(Pos start, Pos target) {
        ArrayDeque<Pos> q = new ArrayDeque<>();
        q.add(start);
        
        while(!q.isEmpty()) {
            Pos t = q.poll();
            
            if(target.x == t.x && target.y == t.y) {
                return t.dist;
            }
            
            for(int i = 0; i < 4; i++) {
                int nx = t.x + dx[i];
                int ny = t.y + dy[i];
                
                if(nx >= row || nx < 0 || ny >= col || ny < 0 || visited[nx][ny] || miro[nx].get(ny) == 'X') {
                    continue;
                }
                visited[nx][ny] = true;
                q.add(new Pos(nx, ny, t.dist + 1));
            }
        }
        return -1;
    }
}

 

2. 구현 로직

1. 시작, 끝, 레버 위치 저장
2. 최소 거리로 탐색해야 하는 문제로 BFS를 활용
3. 레버를 꼭 방문해야 하기에 시작 to 레버 최소 거리 계산
4. 이후, 레버 to 끝 최소 거리 계산 후 합산하여 정답 도출

3. 유의할 점

• 같은 곳을 여러 번 방문할 수 있으므로 방문 배열 초기화 중요