[프로그래머스][C++] 리코쳇 로봇
리코쳇 로봇
문제 링크
분석
말의 이동은 현재 위치 기준 상, 하, 좌, 우 중 한 방향으로 이동할 수 있습니다.
이동 시 장애물이나 게임판 가장자리에 부딪힐 때까지 미끄러져 움직입니다.
2차원 배열(vector<string>)로 이루어진 자료구조가 주어집니다.
board의 문자열 요소는 다음과 같습니다.
".": 빈공간"R": 로봇의 시작 위치"D": 장애물의 위치"G": 목표지점
말이 목표지점에 도달하는데 최소 몇 번 이동해야 하는지 반환해야합니다.
만약 도달할 수 없는 경우 -1을 반환합니다.
가장 적은 횟수로 목표에 도달해야 하므로, DFS보다 BFS가 효율적입니다.
한번 움직일 경우 직선으로 한번에 쭉 이동하기 때문에, 각 방향별로 끝까지 이동한 좌표를 큐에 사용합니다.
풀이
#include <string>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
// 이동 방향으로 상, 하, 좌, 우를 의미
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
int solution(vector<string> board) {
// 보드의 세로 및 가로 길이
int h = board.size();
int w = board[0].size();
// 시작 위치와 목표지점
pair<int, int> start, goal;
// 보드에서 시작 위치와 목표지점의 좌표를 찾는다.
for (int y = 0; y < h; ++y)
{
for (int x = 0; x < w; ++x)
{
// 시작 지점을 찾은 경우 좌표 저장
if (board[y][x] == 'R')
{
start = {y, x};
}
// 목표지점을 찾은 경우 좌표 저장
else if (board[y][x] == 'G')
{
goal = {y, x};
}
}
}
// 방문 여부를 저장하는 2차원 배열
vector<vector<int>> visited(h, vector<int>(w, false));
// BFS를 위한 큐
// y좌표, x좌표, 이동 횟수를 의미
queue<tuple<int, int, int>> q;
// 시작 위치를 큐에 추가하고 방문 처리
q.push({start.first, start.second, 0});
visited[start.first][start.second] = true;
// BFS 시작
while(!q.empty())
{
// 현재 위치와 이동 횟수
auto [y, x, count] = q.front();
q.pop();
// 목표지점에 도착한 경우 이동 횟수를 바로 반환
if (y == goal.first && x == goal.second)
{
return count;
}
// 상, 하, 좌, 우 탐색
for (int i = 0; i < 4; ++i)
{
// 현재 위치 저장
int ny = y;
int nx = x;
// 리코쳇 로봇처럼 해당 방향으로 끝까지 이동
while(true)
{
// 다음 좌표
int ty = ny + dy[i];
int tx = nx + dx[i];
// 이동 할 수 없는 경우 확인
if (ty < 0 || tx < 0 || ty >= h || tx >= w || board[ty][tx] == 'D')
{
break;
}
// 이동 할 수 있으므로 이동
ny = ty;
nx = tx;
}
// 방문하지 않은 경우
if (!visited[ny][nx])
{
// 방문 처리 및 이동 횟수 증가 후 큐에 추가
visited[ny][nx] = true;
q.push({ny, nx, count + 1});
}
}
}
return -1;
}
성능 요약
시간 복잡도는 $O(h \times w \times max(h, w))$입니다.
- 시작 위치와 목표지점의 위치를 찾는 반복문 $O(h \times w)$
- BFS 탐색 $O(h \times w)$
- BFS 탐색에서 각 방향의 리코쳇 움직임 $O(4 \times max(h, w))$
- $O(h \times w) + O(h \times w) \times O(4 \times max(h, w))$
공간 복잡도는 $O(h \times w)$입니다.
- 방문 여부를 저장하는
vector<vector<int>> visited$O(h \times w)$ - BFS를 위해 생성된 큐
queue<tuple<int, int, int>> q$O(h \times w)$ - $O(h \times w) + O(h \times w)$
테스트 성능
테스트 1 〉 통과 (0.16ms, 3.64MB)
테스트 2 〉 통과 (0.14ms, 4.21MB)
테스트 3 〉 통과 (0.03ms, 4.2MB)
테스트 4 〉 통과 (0.06ms, 4.22MB)
테스트 5 〉 통과 (0.06ms, 4.2MB)
테스트 6 〉 통과 (0.02ms, 4.21MB)
테스트 7 〉 통과 (0.21ms, 3.73MB)
테스트 8 〉 통과 (0.04ms, 4.22MB)
테스트 9 〉 통과 (0.09ms, 4.22MB)
테스트 10 〉 통과 (0.13ms, 4.14MB)
테스트 11 〉 통과 (0.01ms, 4.21MB)
테스트 12 〉 통과 (0.01ms, 3.68MB)
테스트 13 〉 통과 (0.01ms, 4.16MB)
테스트 14 〉 통과 (0.03ms, 4.21MB)
테스트 15 〉 통과 (0.03ms, 4.21MB)
테스트 16 〉 통과 (0.09ms, 4.21MB)
테스트 17 〉 통과 (0.03ms, 4.15MB)
테스트 18 〉 통과 (0.04ms, 4.24MB)
테스트 19 〉 통과 (0.08ms, 4.2MB)
테스트 20 〉 통과 (0.01ms, 4.44MB)
테스트 21 〉 통과 (0.19ms, 3.79MB)
테스트 22 〉 통과 (0.04ms, 4.21MB)
테스트 23 〉 통과 (0.02ms, 3.67MB)
테스트 24 〉 통과 (0.20ms, 4.22MB)
테스트 25 〉 통과 (0.09ms, 4.14MB)
테스트 26 〉 통과 (0.08ms, 4.17MB)
테스트 27 〉 통과 (0.03ms, 4.14MB)
댓글남기기