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

 

Level. 2

 

문제

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다.
각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다.
통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다.레버 또한 통로들 중 한 칸에 있습니다.
따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다.
이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다.
미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요.
만약, 탈출할 수 없다면 -1을 return 해주세요.

* 제한사항
- 5 ≤ maps의 길이 ≤ 100
- 5 ≤ maps[i]의 길이 ≤ 100
- maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
  S : 시작 지점
  E : 출구
  L : 레버
  O : 통로
  X : 벽
- 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
- 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

 

풀이

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

//int visited[101][101];
//int count[101][101];

int bfs(int x, int y, int ex, int ey, vector<string> &map ){
    int N = map.size(), M = map[0].size();
    int visited[101][101] = {0,}; // 0 
    int count[101][101] = {0,};
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    queue<pair<int, int>> q;

    q.push(make_pair(x, y));
    visited[x][y] = 1; // 방문했을 경우 0 -> 1
    while(!q.empty()){
        int x2 = q.front().first;
        int y2 = q.front().second;
        q.pop();    
        
        for(int i=0; i<4; i++){
            int nx = x2 + dx[i];
            int ny = y2 + dy[i];
            if(nx >= N || nx < 0 || ny >= M || ny < 0) continue;
            if(!visited[nx][ny] && map[nx][ny] != 'X'){
                visited[nx][ny] = 1; 
                count[nx][ny] = count[x2][y2] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }
    return count[ex][ey]>0?count[ex][ey]:-1;
}

int solution(vector<string> maps) {
    int Sx, Sy; // 시작지점
    int Ex, Ey; // 출구
    int Lx, Ly; // 레버
    
    for(int i=0; i<maps.size(); i++){
        for(int j=0; j<maps[0].size(); j++){
            if(maps[i][j] == 'S'){
                Sx = i;
                Sy = j;
            }
            
            if(maps[i][j] == 'E'){
                Ex = i;
                Ey = j;
            }
            
            if(maps[i][j] == 'L'){
                Lx = i;
                Ly = j;
            }
        }
    }
    
    int len1 = bfs(Sx, Sy, Lx, Ly, maps);
    int len2 = bfs(Lx, Ly, Ex, Ey, maps);
    if(len1<0 || len2 < 0) return -1;
    return len1 + len2;
}

 

 

해결방법

목적지까지의 최단거리를 구할수 있는 알고리즘인 BFS( 너비우선탐색 ) 을 사용하여 풀이하였다. 

1. 레버, 시작점, 출구의 각각 x좌표와 y좌표를 구한다.
2. 목적지에서 레버까지의 최단거리를 BFS을 통해 구한다. 구하지 못할 경우 -1 저장
3. 레버에서부터 목적지까지의 최단거리를 BFS을 통해 구한다. 구하지못할경우 -1 저장
4. 얻은 두 최단거리중 하나라도 -1 일경우 탈출할 수 없다는 의미이므로 -1을 리턴하고, 그렇지 않을 경우 최단거리들의 합을 리턴한다. 

 

 

 

---

https://school.programmers.co.kr/learn/courses/30/lessons/159993?language=cpp

프로그래머스