[프로그래머스][C++] 미로 탈출
미로 탈출
문제 링크
분석
2차원 배열(vector<string>)로 이루어진 맵이 주어집니다.
맵의 각 칸은 다음 중 하나입니다.
- 시작 지점
S - 출구
E - 레버
L - 벽
X - 통로
O
시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
출구는 레버가 당겨지지 않아도 지나갈 수 있습니다.
벽을 제외한 모든 칸은 여러 번 지나갈 수 있습니다.
S에서 L로 이동하고, 마지막으로 E로 이동해야합니다.
각 구간에서 최소 이동 횟수를 구해 각 구간의 총 이동 횟수를 반환해야하며, 만약 특정 구간을 도달할 수 없는 경우 -1을 반환해야합니다.
미로 탐색에서 최단 경로를 탐색하는 문제이므로, BFS를 이용해야 효율적으로 해결할 수 있습니다.
S에서 L로 이동하는 BFS와 L에서 E로 이동하는 BFS를 두 번 수행해서 각 구간의 최소 이동 횟수를 구할 수 있습니다.
각 BFS에서는 큐를 사용해서 현재 위치에서 갈 수 있는 다음 위치들을 모두 탐색하며, 벽이거나 이미 방문한 곳은 넘어갑니다.
특정 위치에서 이동 할 수 있는 방향은 상, 하, 좌, 우로 이동할 수 있습니다.
목적지에 도달하면 이동 횟수를 반환하고, 모든 큐가 소진될 때까지 목적지에 도달하지 못했다면 -1을 반환해야합니다.
풀이
#include <string>
#include <vector>
#include <queue>
using namespace std;
// 좌표와 거리 정보를 담는 구조체
// 큐에서 사용
struct Point
{
int x, y, dist;
};
// 4방향 탐색을 위한 방향 벡터로 상, 하, 좌, 우를 의미
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
// BFS를 통해 시작 지점에서 목표 문자까지의 최단 거리를 구하는 함수
int bfs(const vector<string>& maps, pair<int, int> start, char target)
{
// maps의 세로 길이와 가로 길이
int n = maps.size();
int m = maps[0].size();
// 방문 여부가 기록된 벡터
// 2차원 배열로 true인 경우 방문 했었음을 의미
vector<vector<bool>> visited(n, vector<bool>(m, false));
// BFS 탐색을 위한 큐
// 방문할 좌표와 현재까지의 거리를 저장
queue<Point> q;
// 시작 지점에서 시작하고, 첫 시작 위치이므로 거리는 0
q.push({start.first, start.second, 0});
// 시작 지점 방문 처리
visited[start.first][start.second] = true;
// BFS 탐색
while (!q.empty())
{
// 탐색하려는 현재 위치와 정보
Point p = q.front();
// 큐에서 제거
q.pop();
// 현재 위치가 목표 지점인 경우 출발 지점으로부터의 거리 반환
if (maps[p.x][p.y] == target)
{
return p.dist;
}
// 현재 위치 기준으로 4방향 탐색
for (int i = 0; i < 4; ++i)
{
// 다음 x 좌표와 y 좌표
int nx = p.x + dx[i];
int ny = p.y + dy[i];
// 맵을 벗어나지 않은 경우
if (nx >= 0 && ny >= 0 && nx < n && ny < m)
{
// 방문하지 않았으며, 벽이 아닌 경우
if (!visited[nx][ny] && maps[nx][ny] != 'X')
{
// 방문 처리
visited[nx][ny] = true;
// 거리를 1 증가시키고, 큐에 삽입
q.push({nx, ny, p.dist + 1});
}
}
}
}
// 목표 지점까지 도달할 수 없는 경우이므로, -1을 반환
return -1;
}
int solution(vector<string> maps) {
int answer = 0;
// 각각 시작 지점, 레버, 출구의 위치 값을 저장하는 변수
pair<int, int> start, lever, end;
// 맵의 세로와 가로 크기
int n = maps.size();
int m = maps[0].size();
// 맵에서 S, L, E를 탐색하고 위치 값을 저장
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')
{
end = {i, j};
}
}
}
// S에서 L로 도달하는 최단 거리를 계산합니다.
int toLever = bfs(maps, start, 'L');
// 도달할 수 없는 경우 -1을 반환합니다.
if (toLever == -1)
{
return -1;
}
// L에서 E로 도달하는 최단 거리를 계산합니다.
int toEnd = bfs(maps, lever, 'E');
// 도달할 수 없는 경우 -1을 반환합니다.
if (toEnd == -1)
{
return -1;
}
// 총 거리를 구합니다.
answer = toLever + toEnd;
return answer;
}
struct Point는 ueple이나 pair로 대체 사용할 수 있습니다.
예를 들어, queue<tuple<int, int, int>>처럼 사용할 수 있습니다.
성능 요약
시간 복잡도는 $O(n \times m)$입니다.
- 시작 지점과 레버, 출구의 좌푤르 탐색하는 반복문 $O(n \times m)$
- BFS를 두번 실행하는 시간 복잡도 $O(2 \times n \times m) \approx O(n \times m)$
- $O(n \times m) + O(n \times m)$
공간 복잡도는 $O(n \times m)$입니다.
- 방문 여부가 기록된 벡터
vector<vector<bool>> visited$O(n \times m)$ - BFS 탐색을 위한 큐
queue<Point> q최대 $O(n \times m)$ - $O(n \times m) + O(n \times m)$
테스트 1 〉 통과 (0.01ms, 4.15MB)
테스트 2 〉 통과 (0.01ms, 4.22MB)
테스트 3 〉 통과 (0.01ms, 3.67MB)
테스트 4 〉 통과 (0.01ms, 4.21MB)
테스트 5 〉 통과 (0.01ms, 3.69MB)
테스트 6 〉 통과 (0.01ms, 3.69MB)
테스트 7 〉 통과 (0.09ms, 3.68MB)
테스트 8 〉 통과 (0.12ms, 3.67MB)
테스트 9 〉 통과 (0.01ms, 4.21MB)
테스트 10 〉 통과 (0.01ms, 4.16MB)
테스트 11 〉 통과 (0.05ms, 4.2MB)
테스트 12 〉 통과 (0.22ms, 4.27MB)
테스트 13 〉 통과 (0.22ms, 3.67MB)
테스트 14 〉 통과 (0.15ms, 3.68MB)
테스트 15 〉 통과 (0.04ms, 4.22MB)
테스트 16 〉 통과 (0.36ms, 4.21MB)
테스트 17 〉 통과 (0.44ms, 3.71MB)
테스트 18 〉 통과 (0.01ms, 4.18MB)
테스트 19 〉 통과 (0.02ms, 4.14MB)
테스트 20 〉 통과 (0.30ms, 4.21MB)
테스트 21 〉 통과 (0.07ms, 4.15MB)
테스트 22 〉 통과 (0.01ms, 4.21MB)
테스트 23 〉 통과 (0.01ms, 4.21MB)
댓글남기기