[프로그래머스/Lv. 2] 미로 탈출 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• BFS

필요 자료구조
- dx/dy 배열
- 2차원 char형 배열 (1차원 String형 배열 maps 저장용)
- 2차원 boolean형 배열 (방문 표시용)
- 2차원 int형 배열 start (시작 위치 저장용 배열)
- 2차원 int형 배열 lever (레버 위치 저장용 배열)

 

1. 1차원 String형 배열을 2차원 char형 배열로 저장한다. 저장하면서 S가 나타났을 때는 해당 좌표를 시작 위치에 저장하고, E가 나타났을 때는 해당 좌표를 레버 위치에 저장한다.

 

2. BFS를 두 번 수행한다.

1) 시작점 ▷ 레버까지 가는 BFS

2) 레버 ▷ 종료점까지 가는 BFS

 

3. 만약 2에서 구한 두 결과값 중 하나라도 -1이라면, -1을 출력한다.

그게 아니라면 시작점~ 레버까지 가는 데 걸린 시간과 레버~종료점까지 가는 데 걸린 시간을 더해 출력한다.

 

 

 

 

💥 유의사항

① "이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다"라고 해서

레버를 안 지나가고 BFS를 한 번만 수행해도 되겠지?라는 생각을 하면 안 된다.

무조건 (시작점 > 레버)를 거친 후, (레버 > 종료점)으로 이동해야 한다.

 

② bfs를 수행할 때마다 방문 배열은 새롭게 초기화해줘야 한다.

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int r, c;
    
    static char[][] grid;
    static boolean[][] visited;
    
    static int[] start = new int[2];
    static int[] lever = new int[2];
    
    public int solution(String[] maps) {
        r = maps.length;
        c = maps[0].length();        
                
        grid = new char[r][c];        
        for(int i = 0 ; i < r ; i++) {
            for(int j = 0 ; j < c ; j++) {
                grid[i][j] = maps[i].charAt(j);
                
                if(grid[i][j] == 'S') {
                    start = new int[] {i, j};
                }
                else if(grid[i][j] == 'L') {
                    lever = new int[] {i, j};
                }
            }
        }
        
        visited = new boolean[r][c];
        int result1 = bfs(start, 'L');
        
        visited = new boolean[r][c]; // 🔔 여기서도 방문 배열 꼭 초기화해줘야 함!!
        int result2 = bfs(lever, 'E');       
        
        if(result1 == -1 || result2 == -1) {
            return -1;
        }
        
        return result1 + result2;      
        
    }
    
    private static int bfs(int[] start, char target) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {start[0], start[1], 0}); // 🔔 큐에 (현재 행 위치, 열 위치, 걸린 시간)을 저장한다.
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            int x = now[0];
            int y = now[1];
            int cnt = now[2];
            visited[x][y] = true;
            
            if(grid[x][y] == target) { // 목적지 도착 시, 여태까지 걸린 시간 출력하고 종료
                return cnt;
            }
            
            for(int d = 0 ; d < 4 ; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                
                if(canGo(nx, ny)) { // 다음 좌표로 이동할 수 있다면, 걸린 시간 + 1해서 저장하기
                    visited[nx][ny] = true;
                    q.add(new int[] {nx, ny, cnt + 1});
                }
            }
        }
        
        return -1;
    }
    
    private static boolean canGo(int x, int y) { // 범위 내에 있고, 방문한 적 없고, X가 아니면 방문 가능
        return (inRange(x, y) && !visited[x][y] && grid[x][y] != 'X');
    }
    
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < r && 0 <= y && y < c);
    }
}

 

 

➕ 다른 풀이 방식

DFS(백트래킹)로 푸신 방식

[프로그래머스] 미로 탈출 명령어 - JAVA

 

---

💦 어려웠던 점

- 방문 표시 겸 걸린 시간을 저장하려고 visited 배열을 2차원 int형 배열로 해봤었는데 담엔 그냥 boolean형으로 가야겠다.

- 문제를 잘 못 이해해서 시작점에서 종료점까지 BFS를 한 번만 수행하면 되는 줄 알았다. (낚였다.) 그냥 시작점 > 레버, 레버 > 종료점으로 2번 BFS 수행하는 것이었다.

 

🧐 새로 알게 된 내용

- 큐에 좌표 뿐만 아니라 걸린 시간 값까지 들고 가서 활용하기

- BFS 2번 수행할 때, 시작 전에 방문 배열은 매번 초기화해주는 거 잊지 말기!

 

1회독	2회독	3회독	4회독	5회독
V

 

---

(참고)

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