[프로그래머스] 미로 탈출 (java)

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

프로그래머스

미로 탈출 문제

미로를 탈출하되, 레버를 먼저 누르고 나서 출구로 탈출하는 문제

 

#사용 알고리즘

너비 우선 탐색(BFS)

📌문제 접근 포인트

1. 최단 거리로 빠르게 미로를 탈출하는데 걸리는 시간을 구하는 알고리즘으로 BFS를 사용한다.

2. 시작부터 레버까지 도착 후, 레버에서 출구까지 걸리는 시간 중 최소 시간을 구해야한다.

3. 시작부터 레버까지 갈 수 있는지 체크한 후, 레버에서 출구까지 갈 수 있는지 체크해서 둘의 최소 시간의 합을 구하면 성공

※ 방문 처리 시 시작부터 => 레버 / 레버 => 출구 각각을 따로 방문처리 해야한다. 하나로 할 경우 경로가 겹치는 부분을 계산할 수 없음

반응형

⚙ 내가 푼 정답 코드

import java.util.*;

class Solution {
    public static int[] dx = {1,-1,0,0};
    public static int[] dy = {0,0,1,-1};
    public static int n, m;
    public static int[][] visited;
    
    static class maze{
        int y, x;
        public maze(int y, int x){
            this.x = x;
            this.y = y;
        }
    }
    
    public static int find(char start, char end, String[] maps){
        Queue<maze> queue = new LinkedList<maze>();
        visited = new int[n][m];
        for (int i = 0 ; i < n; i++){
            for (int j = 0; j < m; j++){
                if (maps[i].charAt(j) == start){
                    queue.offer(new maze(i,j));
                    visited[i][j] = 1;
                }
            }
        }

        while (!queue.isEmpty()){
            maze p = queue.poll();
            int y = p.y;
            int x = p.x;
            
            if (maps[y].charAt(x) == end){
                return visited[y][x] -1;
            }
            
            for (int i = 0 ; i < 4; i++){
                int ny = y + dy[i];
                int nx = x + dx[i];
                
                if(0 <= ny && ny < n && 0 <= nx && nx < m && visited[ny][nx] == 0){
                    if(maps[ny].charAt(nx) != 'X'){
                        visited[ny][nx] = visited[y][x] + 1;
                        queue.add(new maze(ny,nx));
                    }
                    
                }
            }
        }      
        return -1;
    }
        
    public int solution(String[] maps) {
        n = maps.length;
        m = maps[0].length();
        int way1 = find('S','L',maps);
        int way2 = find('L','E',maps);
        if (way1 == -1 || way2 == -1){
            return -1;
        }
        else{
            return way1 + way2;
        }
    }
}