[프로그래머스][C++] 게임 맵 최단거리
게임 맵 최단거리
문제 링크
분석
2차원 배열(게임 맵)에서 (0,0) 위치에서 (n-1, m-1) 위치까지 이동하는 최단 거리 탐색 문제입니다.
이동은 동, 서, 남, 북 네 방향으로 한 칸씩 이동 가능하며, 벽인 곳은 지나갈 수 없습니다.
DFS(깊이 우선 탐색)는 특정 경로를 끝까지 탐색한 후 돌아오므로, 최단 거리를 찾는 데 적절하지 않습니다.
해당 문제에서 DFS를 사용하면 시간 초과가 발생합니다.
BFS(너비 우선 탐색)는 시작점에서 가까운 노드부터 탐색하므로, 최단 경로를 찾는 데 적절합니다.
방문 처리는 maps 자체를 수정해서 방문했는지 안했는지 확인할 수 있습니다.
시작 위치에서부터 도착점까지의 거리를 반환해야합니다.
만약 도착점에 도달할 수 없는 경우 -1을 반환해야합니다.
풀이
DFS를 사용한 방법입니다.
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
// 결과를 반환할 변수
int answer = INT_MAX;
// 이동 방향 (동, 서, 남, 북)
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
// maps의 세로, 가로 크기
int n, m;
void dfs(vector<vector<int>>& maps, int x, int y, int count)
{
// 도착점에 도달했을 경우 최소값을 확인하고 갱신
if (n - 1 == y && m - 1 == x)
{
answer = min(answer, count);
return;
}
// 방문 처리
maps[y][x] = 0;
// 이동 방향 탐색
for (int i = 0; i < 4; ++i)
{
// 다음에 방문할 곳(동, 서, 남, 북)
int ny = y + dy[i];
int nx = x + dx[i];
// 방문 할 수 없는 경우
if (nx < 0 || nx >= m || ny < 0 || ny >= n || maps[ny][nx] == 0)
{
continue;
}
dfs(maps, nx, ny, count + 1);
}
// 원래 상태로 복구
maps[y][x] = 1;
}
int solution(vector<vector<int> > maps)
{
n = maps.size();
m = maps[0].size();
dfs(maps, 0, 0, 1);
// 도착할 수 없는 경우
if (answer == INT_MAX)
{
answer = -1;
}
return answer;
}
BFS를 사용한 방법입니다.
#include <vector>
#include <queue>
using namespace std;
int solution(vector<vector<int>> maps)
{
int answer = 0;
// 이동 방향 (동, 서, 남, 북)
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
// maps의 세로, 가로 크기
int n = maps.size();
int m = maps[0].size();
queue<pair<int, int>> q; // BFS를 위한 큐
q.push({0, 0}); // 시작 위치
while(!q.empty())
{
int y = q.front().first;
int x = q.front().second;
q.pop();
int dist = maps[y][x]; // 현재 위치까지의 거리
// 도착점에 도달했을 경우 답 반환
if (n - 1 == y && m - 1 == x)
{
return dist;
}
// 이동 방향 탐색
for (int i = 0; i < 4; ++i)
{
int ny = y + dy[i];
int nx = x + dx[i];
// 방문 할 수 없는 경우
if (nx < 0 || nx >= m || ny < 0 || ny >= n || maps[ny][nx] == 0)
{
continue;
}
// 방문하지 않은 경우 이동
if (maps[ny][nx] == 1)
{
maps[ny][nx] = dist + 1; // 이동 거리 갱신
q.push({ny, nx});
}
}
}
// 도착할 수 없는 경우
return -1;
}
방문한 적 없는 새로운 위치로 이동할 때 시작 위치에서부터의 거리를 maps의 요소로 저장합니다.
도착점에 도달한 경우 이 요소를 반환합니다.
성능 요약
DFS를 사용한 성능은 다음과 같습니다.
시간 복잡도는 $O(4(n \times m))$입니다.
- DFS의 방문 횟수 $O(4^(n \times m))$
공간 복잡도는 $O(n \times m)$입니다.
- 재귀 호출 스택 $O(n \times m)$
정확성 테스트
테스트 1 〉 통과 (0.01ms, 3.74MB)
테스트 2 〉 통과 (0.01ms, 4.27MB)
테스트 3 〉 통과 (0.01ms, 3.74MB)
테스트 4 〉 통과 (0.01ms, 4.15MB)
테스트 5 〉 통과 (0.01ms, 4.22MB)
테스트 6 〉 통과 (0.01ms, 4.21MB)
테스트 7 〉 통과 (0.04ms, 3.68MB)
테스트 8 〉 통과 (0.01ms, 4.2MB)
테스트 9 〉 통과 (0.02ms, 3.67MB)
테스트 10 〉 통과 (0.04ms, 4.22MB)
테스트 11 〉 통과 (0.01ms, 3.68MB)
테스트 12 〉 통과 (0.01ms, 4.15MB)
테스트 13 〉 통과 (0.01ms, 3.68MB)
테스트 14 〉 통과 (0.01ms, 4.16MB)
테스트 15 〉 통과 (0.01ms, 3.7MB)
테스트 16 〉 통과 (0.01ms, 4.15MB)
테스트 17 〉 통과 (0.02ms, 4.23MB)
테스트 18 〉 통과 (0.01ms, 4.23MB)
테스트 19 〉 통과 (0.01ms, 4.2MB)
테스트 20 〉 통과 (0.01ms, 4.22MB)
테스트 21 〉 통과 (0.01ms, 3.68MB)
효율성 테스트
테스트 1 〉 실패 (시간 초과)
테스트 2 〉 실패 (시간 초과)
테스트 3 〉 실패 (시간 초과)
테스트 4 〉 실패 (시간 초과)
BFS를 사용한 성능은 다음과 같습니다.
시간 복잡도는 $O(n \times m)$입니다.
- BFS의 방문 횟수 $O(n \times m)$
공간 복잡도는 $O(n \times m)$입니다.
- BFS 큐
queue<pair<int, int>> q$O(n \times m)$
정확성 테스트
테스트 1 〉 통과 (0.01ms, 3.68MB)
테스트 2 〉 통과 (0.01ms, 4.14MB)
테스트 3 〉 통과 (0.01ms, 4.21MB)
테스트 4 〉 통과 (0.01ms, 4.21MB)
테스트 5 〉 통과 (0.01ms, 4.21MB)
테스트 6 〉 통과 (0.01ms, 4.21MB)
테스트 7 〉 통과 (0.01ms, 3.68MB)
테스트 8 〉 통과 (0.01ms, 4.13MB)
테스트 9 〉 통과 (0.01ms, 4.28MB)
테스트 10 〉 통과 (0.01ms, 4.11MB)
테스트 11 〉 통과 (0.01ms, 3.69MB)
테스트 12 〉 통과 (0.01ms, 4.21MB)
테스트 13 〉 통과 (0.01ms, 4.21MB)
테스트 14 〉 통과 (0.01ms, 4.16MB)
테스트 15 〉 통과 (0.01ms, 4.14MB)
테스트 16 〉 통과 (0.01ms, 4.2MB)
테스트 17 〉 통과 (0.01ms, 4.2MB)
테스트 18 〉 통과 (0.01ms, 3.67MB)
테스트 19 〉 통과 (0.01ms, 4.2MB)
테스트 20 〉 통과 (0.01ms, 4.15MB)
테스트 21 〉 통과 (0.01ms, 3.68MB)
효율성 테스트
테스트 1 〉 통과 (0.14ms, 4.11MB)
테스트 2 〉 통과 (0.09ms, 4MB)
테스트 3 〉 통과 (0.20ms, 4.05MB)
테스트 4 〉 통과 (0.11ms, 4.08MB)
댓글남기기