[프로그래머스] 미로 탈출 - Java

문제

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

프로그래머스

 

---

 

문제 개요

1 x 1 크기의 직사각형 미로에서 시작 지점에서 출발해 레버를 작동시킨 후 출구로 이동하여 탈출하는 데 걸리는 최소 시간을 구하는 문제입니다. 이동은 통로에서만 가능하며, 벽은 지나갈 수 없습니다. 레버를 작동시키기 전에도 출구를 지나갈 수는 있지만, 레버를 작동해야만 출구를 통해 탈출할 수 있습니다.

접근 방법

1. 지도 구성: 주어진 문자열 배열을 2차원 배열로 변환하여 미로 지도를 만듭니다.
2. BFS 탐색:
   • 시작점에서 레버 위치까지의 최단 거리를 계산합니다.
   • 레버 위치에서 출구까지의 최단 거리를 계산합니다.
   • BFS(너비 우선 탐색)를 이용해 각 칸에서 이동 가능한 위치를 탐색하며 목표 위치(레버 또는 출구)에 도달하면 거리를 반환합니다.
3. 유효성 검사: 레버 또는 출구에 도달하지 못하는 경우 -1을 반환합니다.

코드

import java.util.*;
class Solution {
    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};
    static String[][] map;
    static boolean[][] v;
    public int solution(String[] maps) {
        int answer = 0;
        int sum = 0;
        makeMap(maps);
                
        for(int i=0; i<map.length; i++) {
            for(int j=0; j<map[0].length; j++) {
                if(map[i][j].equals("S")) {
                    v = new boolean[maps.length][maps[0].length()];
                    v[i][j] = true;
                    sum = bfs(new Pos(i,j,0), "L");
                    if(sum == -1) return -1;
                    else answer = sum;
                    break;
                }
            }
        }
        sum = 0;
        for(int i=0; i<map.length; i++) {
            for(int j=0; j<map[0].length; j++) {
                if(map[i][j].equals("L")) {
                    v = new boolean[maps.length][maps[0].length()];
                    v[i][j] = true;
                    sum = bfs(new Pos(i,j,0), "E");
                    if(sum == -1) return -1;
                    break;
                }
            }
        }
        
        return answer + sum;
    }
    
    public int bfs(Pos pos, String target) {
        Queue<Pos> q = new LinkedList<>();
        q.add(pos);
        
        while(!q.isEmpty()) {
            Pos cur = q.poll();
            if(map[cur.r][cur.c].equals(target))return cur.cnt;
            
            for(int i=0; i<4; i++) {
                int nr = cur.r + dr[i];
                int nc = cur.c + dc[i];
                if(nr<0 || nc<0 || nr>=map.length || nc>=map[0].length || v[nr][nc] || map[nr][nc].equals("X")) continue;
                v[nr][nc] = true;
                q.add(new Pos(nr, nc, cur.cnt+1));
            }
        }
        return -1;
    }
    
    public void makeMap(String[] maps) {
        map = new String[maps.length][maps[0].length()];
        for(int i=0; i<maps.length; i++) map[i] = maps[i].split("");
    }
    
    class Pos {
        int r, c, cnt;
        public Pos(int r, int c, int cnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
        }
    }
}