프로그래머스 [연습문제 / 미로 탈출](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 159993 미로 탈출

---

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/159993

문제 설명:

1×1 크기의 직사각형 격자 미로에서 탈출하는 문제입니다. 미로에는 시작점(S), 레버(L), 출구(E)가 있으며, 벽(X)은 통과할 수 없고 통로(O)로만 이동할 수 있습니다. 중요한 조건은 출구의 문이 잠겨 있어서 반드시 레버를 먼저 당긴 후에 출구로 이동해야 한다는 것입니다. 즉, S → L → E 순서로 이동해야 합니다. 한 칸 이동에 1초가 걸리며, 최단 시간을 구해야 합니다. 탈출이 불가능하면 -1을 반환합니다.

---

문제 해결 코드

#include <string>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

// BFS로 시작점에서 목표 지점까지의 최단 거리를 구하는 함수
int bfs(vector<string>& maps, pair<int,int> start, char target) {
    int n = maps.size();
    int m = maps[0].size();
    
    // 방문 배열 초기화
    int visited[101][101];
    memset(visited, 0, sizeof(visited));
    
    // 4방향 이동 (상, 하, 좌, 우)
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    
    queue<pair<int,int>> q;
    q.push(start);
    visited[start.first][start.second] = 1;  // 시작점은 1로 표시
    
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        // 목표 지점을 찾으면 거리 반환 (시작점 포함하므로 -1)
        if(maps[x][y] == target) {
            return visited[x][y] - 1;
        }
        
        // 4방향 탐색
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 경계 체크
            if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            
            // 벽이거나 이미 방문한 곳은 제외
            if(maps[nx][ny] == 'X' || visited[nx][ny]) continue;
            
            visited[nx][ny] = visited[x][y] + 1;
            q.push({nx, ny});
        }
    }
    
    // 목표 지점에 도달할 수 없음
    return -1;
}

int solution(vector<string> maps) {
    int n = maps.size();
    int m = maps[0].size();
    
    // 시작점(S), 레버(L), 출구(E) 위치 찾기
    pair<int,int> start, lever, exit;
    
    for(int i = 0; i < n; i++) {
        for(int 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') {
                exit = {i, j};
            }
        }
    }
    
    // 1단계: 시작점에서 레버까지의 최단 거리
    int distToLever = bfs(maps, start, 'L');
    
    // 레버에 도달할 수 없으면 탈출 불가
    if(distToLever == -1) return -1;
    
    // 2단계: 레버에서 출구까지의 최단 거리
    int distToExit = bfs(maps, lever, 'E');
    
    // 출구에 도달할 수 없으면 탈출 불가
    if(distToExit == -1) return -1;
    
    // 전체 최단 거리 = (시작→레버) + (레버→출구)
    return distToLever + distToExit;
}

---

코드 설명

• 핵심 알고리즘: BFS(너비 우선 탐색)를 두 번 수행하는 방식입니다. 첫 번째 BFS로 시작점에서 레버까지의 최단 거리를 구하고, 두 번째 BFS로 레버에서 출구까지의 최단 거리를 구합니다. BFS는 가중치가 없는 그래프에서 최단 거리를 보장하므로 이 문제에 적합합니다.
• 구현 세부사항:
  • bfs 함수를 일반화하여 시작점과 목표 문자를 매개변수로 받습니다.
  • visited 배열에 시작점을 1로 초기화하고, 이동할 때마다 1씩 증가시켜 거리를 추적합니다.
  • 목표 지점을 찾으면 visited 값에서 1을 빼서 반환합니다 (시작점 카운트 제외).
  • S, L, E 위치를 먼저 찾아서 pair로 저장합니다.
  • 첫 번째 BFS가 -1을 반환하면 레버에 도달 불가이므로 즉시 -1 반환합니다.
  • 두 번째 BFS가 -1을 반환하면 출구에 도달 불가이므로 -1 반환합니다.
  • 두 거리를 합산하여 전체 최단 거리를 반환합니다.
• 시간/공간 복잡도: 시간 복잡도는 O(n ⋅ m)입니다. BFS를 두 번 수행하므로 O(2 ⋅ n ⋅ m)이지만 상수는 제거하여 O(n ⋅ m)입니다. 공간 복잡도는 O(n ⋅ m)으로 visited 배열과 큐에 사용되는 공간입니다.

---

실행 예시

입력:

maps = ["SOOOL", "XXXXL", "OOOOO", "OXXXX", "OOOOE"]

실행 과정:

• 미로 구조 (5×5):

  S O O O L
  X X X X L
  O O O O O
  O X X X X
  O O O O E

• 위치 파악: S(0,0), L(0,4), E(4,4)
• 1단계 BFS: S → L
  • (0,0) → (0,1) → (0,2) → (0,3) → (0,4) = 4칸 이동
• 2단계 BFS: L → E
  • (0,4) → (1,4) → (2,4) → (2,3) → (2,2) → (2,1) → (2,0) → (3,0) → (4,0) → (4,1) → (4,2) → (4,3) → (4,4) = 12칸 이동
• 총 거리: 4 + 12 = 16초

출력:

16

---

결과

원본 코드의 전역 변수와 복잡한 구조를 제거하고, BFS 함수를 일반화하여 재사용 가능하도록 개선했습니다. visited 배열을 함수 내부에서 관리하여 각 BFS가 독립적으로 동작하며, 디버그 코드와 불필요한 로직을 제거하여 코드 가독성을 크게 향상시켰습니다. 두 번의 BFS로 최단 경로 문제를 효율적으로 해결하는 전형적인 패턴입니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!