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

1. 문제

---

프로그래머스

 

2. 풀이 과정

---

무조건 레버를 거친 후 도착지점가지 가야한다. 

따라서 두 번의 최단거리를 구해야 한다.

 

1. 시작지점(S) ➡️ 레버(L)

2. 레버(L) ➡️ 출구(E)

 

두 번의 최단거리를 구한 후 둘을 더하면 된다.

 

해당 구조에서 최단거리를 구하기 위해선 너비 우선 탐색을 활용해볼 수 있다.

왜냐하면 지점간에 가중치가 존재하지 않기 때문이다.

 

너비 우선 탐색(BFS)을 통해 최단거리 구하기

1. 시작지점(S) ➡️ 레버(L)

시작지점에서 레버까지의 최단거리는 4

 

 

2. 레버(L) ➡️ 출구(E)

레버에서 출구까지의 최단거리는 12

 

따라서 정답은 4 + 12 = 16이다.

 

이제 코드로 보도록하자.

3. 내 코드

---

import java.util.*;
class Solution {
    
    class Node{
        int row;
        int col;
        
        Node(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
    public int solution(String[] maps) {
        
        int total_distance = 0;
         // 1) 시작 지점, 레버, 출구 찾기
        Node S = null;
        Node L = null;
        Node E = null;
        for(int i = 0; i < maps.length; i++) {
            for(int j = 0; j < maps[i].length(); j++) {
                if(maps[i].charAt(j) == 'S') {
                    S = new Node(i, j);
                } else if(maps[i].charAt(j) == 'L') {
                    L = new Node(i, j);
                } else if(maps[i].charAt(j) == 'E') {
                    E = new Node(i, j);
                }
            }
        }
        
        // 1. 시작 지점에서 레버까지의 최단거리 
        int S_to_L = shrt_dist(S, L, maps);
      
        if(S_to_L == 0) {
            return -1;
        }
        total_distance += S_to_L;
        
        // 2. 레버에서 출구까지의 최단거리
        
        int L_to_E = shrt_dist(L, E, maps);
        
        if(L_to_E == 0) {
            return -1;
        }
        total_distance += L_to_E;
        
        return total_distance;
    }
    
    private int[] row_rotate = new int[]{0, 0, -1, 1};
    private int[] col_rotate = new int[]{1, -1, 0, 0};
    private int shrt_dist(Node start, Node dest, String[] maps){
        Queue<Node> queue = new ArrayDeque<>();
        int[][] distance = new int[maps.length][maps[0].length()];
        
        
        queue.add(start); // 시작지점 큐에넣기
        distance[0][0] = 0;
        
        while(!queue.isEmpty()) {
            Node node = queue.poll();
            
            // 인접한 통로 큐에 넣기
            for(int i = 0; i < 4; i++) {
                int row = node.row + row_rotate[i];
                int col = node.col + col_rotate[i];
                
                // maps에서 벗어나는 경우
                if(row < 0 || row == maps.length || col < 0 || col == maps[0].length()) continue;
                // 벽인 경우
                if(maps[row].charAt(col) == 'X') continue;
                
                // 한번도 방문하지 않은 곳인 경우 queue에 추가하고 경로 갱신
                if(distance[row][col] == 0){
                    queue.add(new Node(row, col));
                    distance[row][col] = distance[node.row][node.col] + 1;
                }
            
            }
        }
        
        return distance[dest.row][dest.col]; 
    }
}

시간 복잡도

• O(N^2)

최악의 경우 maps의 크기만큼 큐에넣고 꺼내 상하좌우를 따지므로 O(4*N^2) == O(N^2)