[프로그래머스] 리코쳇 로봇 C++

 

 

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/169199

프로그래머스

 

이번 문제는 bfs 문제였습니다.

 

 

 

 

 

📝 문제 풀이

1. 게임 보드판의 로봇의 처음 위치와 목표 지점을 찾아 각각 start, goal 객체에 저장

2. bfs 수행

• 로봇의 처음 위치와 이동 횟수 0을 큐(queue)에 삽입
• 로봇의 처음 위치는 방문 체크 visited[start.first][start.second] = true;
• 현재 위치에서 상, 하, 좌, 우로 이동했을 경우 벽이 아니거나 (보드판의 범위 내에 있거나) 장애물이 없으면 ('D'가 아니면)

        ➡️ 맨 끝에 부딪히거나 장애물을 만날 때까지 계속 이동

        ➡️ 맨 끝에 부딪히거나 장애물을 만나서 이동이 종료되면, 방문한 좌표가 아닐 경우에만 해당 좌표를 큐에 삽입

3. 현재 위치가 목표 지점과 같으면 answer 갱신

4. answer이 갱신되지 않았다면 (목표 지점에 도달할 수 없다면) -1 반환

 

 

 

 

👩🏻‍💻 C++ 코드

#include <string>
#include <vector>
#include <queue>
#define MAX 100

using namespace std;

int n, m;
int answer = 2147000000;
pair<int, int> start;
pair<int, int> goal;
bool visited[MAX][MAX];

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void bfs(vector<string> &board) {
    queue<pair<pair<int, int>, int>> q;
    
    q.push({{start.first, start.second}, 0});
    visited[start.first][start.second] = true;
    
    while (!q.empty()) {
        int cx = q.front().first.first;
        int cy = q.front().first.second;
        int cnt = q.front().second;
        q.pop();
        
        if (cx == goal.first && cy == goal.second) {
            answer = min(answer, cnt);
        }
        
        for (int i=0; i<4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            
            if ((nx < 0 || n <= nx || ny < 0 || m <= ny) || board[nx][ny] == 'D') continue;
            
            while (true) {
                nx += dx[i];
                ny += dy[i];
                
                if ((nx < 0 || n <= nx || ny < 0 || m <= ny) || board[nx][ny] == 'D') {
                    nx -= dx[i];
                    ny -= dy[i];
                    break;
                }
            }
           
            if (visited[nx][ny]) continue;
            
            q.push({{nx, ny}, cnt + 1});
            visited[nx][ny] = true;
        }
    }
}

int solution(vector<string> board) {
    n = board.size();
    m = board[0].size();
    
    int findCnt = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (findCnt == 2) break;
            
            if (board[i][j] == 'R') {
                findCnt++;
                start = {i, j};
            } else if (board[i][j] == 'G') {
                findCnt++;
                goal = {i, j};
            }
        }
    }
    
    bfs(board);
    
    if (answer == 2147000000) return -1;
    return answer;
}

 

 

프로그래머스 - 결과 화면