[Programmers] 미로 탈출(Python, Javascript, Java)

문제

요약

시작지점에서 레버에 들렸다가 탈출지점까지 가는 최소 시간을 구해라.

 

문제

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

프로그래머스

 

---

풀이

Python

from collections import deque

def solution(maps):
    n, m = len(maps), len(maps[0])
    start = (0, 0)
    end = (n-1, m-1)
    lever = (1, 1)
    
    for i in range(n):
        for j in range(m):
            if maps[i][j] == "S":
                start = (i, j)
            elif maps[i][j] == "E":
                end = (i, j)
            elif maps[i][j] == "L":
                lever = (i, j)
    
    directions = [(-1,0), (1,0), (0,-1), (0,1)]
    
    def bfs(stack, goal):
        visited = [[-1] * m for _ in range(n)]
        visited[stack[0][0]][stack[0][1]] = 0
        gx, gy = goal
        
        while stack:
            x, y = stack.popleft()

            for dx, dy in directions:
                nx = x+dx
                ny = y+dy
                
                if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == -1 and maps[nx][ny] != "X":
                    stack.append((nx, ny))
                    visited[nx][ny] = visited[x][y] + 1
        return visited[gx][gy]
    
    stol = bfs(deque([start]), lever)
    if stol != -1:
        ltoe = bfs(deque([lever]), end)
        if ltoe != -1:
            return stol+ltoe
        
    return -1

 

Javascript

function solution(maps) {
    const n = maps.length;
    const m = maps[0].length;
    
    let start = [0,0];
    let lever = [1, 1];
    let end = [n, m];
    
    for (let i = 0; i < n; i++){
        for (let j = 0; j < m; j++){
            if (maps[i][j] === "S"){
                start = [i, j];
            } else if (maps[i][j] === "L"){
                lever = [i, j];
            } else if (maps[i][j] === "E"){
                end = [i, j];
            }
        }
    }
    
    const d = [[-1,0], [1,0], [0,-1], [0,1]]
    
    function bfs(stack, gx, gy){
        let visited = Array.from(Array(n), () => Array(m).fill(-1));
        visited[stack[0][0]][stack[0][1]] = 0

        while (stack.length) {
            const [x, y] = stack.shift();

            for (let i = 0; i < 4; i++) {
                const nx = x + d[i][0];
                const ny = y + d[i][1];

                if (0 <= nx && nx < n && 0 <= ny && ny < m && visited[nx][ny] === -1 && maps[nx][ny] != "X") {
                    stack.push([nx, ny])
                    visited[nx][ny] = visited[x][y] + 1
                }
            }
        }
        return visited[gx][gy];
    }
    
    const stol = bfs([start], lever[0], lever[1]);
    if (stol != -1){
        const ltoe = bfs([lever], end[0], end[1]);
        if (ltoe != -1){
            return stol + ltoe;
        }
    }
    
    return -1;
}

 

Java

큐에 값이 배열로 들어갈 때는 LinkedList가 아니라 ArrayDeque를 통해서 구현한다.

import java.util.*;

class Solution {
    int n;
    int m;
    int[][] d = {{-1, 0}, {1,0}, {0,-1},{0,1}};
    
    public int bfs(int[][] lst,int gx, int gy, String[] maps){
        int[][] visited = new int[n][m];
        
        Queue<int[]> q = new ArrayDeque<>();
        for (int[] v : lst) {
            q.offer(v);
            visited[v[0]][v[1]] = 1;   
        }
        
        while (!q.isEmpty()){
            int[] now = q.remove();
            
            for (int i = 0; i < 4; i++){
                int nx = now[0] + d[i][0];
                int ny = now[1] + d[i][1];
                
                if (0 <= nx && nx < n && 0 <= ny && ny < m && visited[nx][ny] == 0 && maps[nx].charAt(ny) != 'X'){
                    int[] t = {nx, ny};
                    q.offer(t);
                    visited[nx][ny] = visited[now[0]][now[1]] + 1;
                }
            }
        }
        return visited[gx][gy] - 1;
    }
    
    public int solution(String[] maps) {
        n = maps.length;
        m = maps[0].length();
        
        int[][] start = new int[1][2];
        int[][] end = new int[1][2];
        int[][] lever = new int[1][2];

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (maps[i].charAt(j) == 'S'){
                    start[0][0] = i;
                    start[0][1] = j;
                } else if (maps[i].charAt(j) == 'E'){
                    end[0][0] = i;
                    end[0][1] = j;
                } else if (maps[i].charAt(j) == 'L'){
                    lever[0][0] = i;
                    lever[0][1] = j;
                }
            }
        }

        
        int StoL = bfs(start, lever[0][0], lever[0][1], maps);
        if (StoL != -1){
            int LtoE = bfs(lever, end[0][0], end[0][1], maps);
            if (LtoE !=-1){
                return StoL + LtoE;
            }
        }
        return -1;
    }
}