프로그래머스 - 미로 탈출

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

프로그래머스

 

 

 

 

 

문제

• 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있다.
• 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있다.
• 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 된다.
  • 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있다.
• 한 칸을 이동하는데 1초, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간 구하기
  • 탈출할 수 없다면 -1을 return
• S : 시작 지점, E : 출구, L : 레버, O : 통로, X : 벽
  • 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재

 

입출력 예

• 입력 : maps ["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]
• 출력 : 16

출처 : 프로그래머스(https://school.programmers.co.kr/learn/courses/30/lessons/159993)

 

 

 

 

 

풀이

• 그래프 탐색 중 BFS 사용
  • BFS 1 : S → L로 가는 길. -1이 리턴되었으면 뒤에 돌릴 필요도 없이 종료
  • BFS 2 : L → E 로 가는 길에 대해 BFS를 돌린다. -1이 리턴되었으면 종료, 아니면 BFS 1 + BFS 2가 정답

 

• 재활용성을 위해 BFS에 시작 시점과 목표 지점을 매개변수로 준다

 

• 큐에 지점의 좌표와 걸린 시간의 정보를 담은 객체를 넣는다
  • Point(x, y, dist)

 

 

 

 

 

코드

import java.util.*;

class Solution {
    static int N, M; //행, 열 크기
    static char[][] graph; //그래프
    static boolean[][] visited; //방문 여부 배열
    static int[] dx = {-1, 1, 0, 0}; //상하좌우
    static int[] dy = {0, 0, -1, 1};
    
    static class Point {
        int x, y, dist; //행, 열, 걸린 시간
        
        Point(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }
    
    public int solution(String[] maps) {
        N = maps.length;
        M = maps[0].length();
        
        graph = new char[N][M];
        
        int SX = 0, SY = 0; //시작 좌표
        int LX = 0, LY = 0; //레버 좌표
        
        for(int i = 0; i < N; i++) {
            graph[i] = maps[i].toCharArray();
            
            for(int j = 0; j < M; j++) {
                if(graph[i][j] == 'S') {
                    SX = i;
                    SY = j;
                } else if(graph[i][j] == 'L') {
                    LX = i;
                    LY = j;
                }
            }
        }
        
        int answer = 0;
        
        visited = new boolean[N][M];
        int result1 = bfs(SX, SY, 'L'); //시작~레버까지 시간
        
        if(result1 == -1) {
            return -1;
        } else {
            answer += result1;
        }
        
        visited = new boolean[N][M];
        int result2 = bfs(LX, LY, 'E'); //레버~출구까지 시간
        
        if(result2 == -1) {
            return -1;
        } else {
            answer += result2;
        }
        
        return answer;
    }
    
    public int bfs(int i, int j, char goal) {
        Queue<Point> queue = new LinkedList<>();
        
        queue.add(new Point(i, j, 0));
        visited[i][j] = true;
        
        while(!queue.isEmpty()) {
            Point point = queue.poll();
            
            int x = point.x;
            int y = point.y;
            int dist = point.dist;
            
            if(graph[x][y] == goal) {
                return dist;
            }
            
            for(int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                
                if(0 <= nx && nx < N && 0 <= ny && ny < M) { //범위 체크
                    if(!visited[nx][ny] && graph[nx][ny] != 'X') { //방문x, 벽이 아님
                        queue.add(new Point(nx, ny, dist + 1));
                        visited[nx][ny] = true;
                    }
                }
            }
            
        }
        
        return -1;
    }
}

 

 

 

 

결과

 

 

 

 

 

배운점