[프로그래머스] 리코쳇 로봇 / bfs

 

Level. 2

 

문제

리코쳇 로봇이라는 보드게임이 있습니다.
이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.
이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.
다음은 보드게임판을 나타낸 예시입니다.

...D..R
.D.G...
....D.D
D....D.
..D....

여기서 "."은 빈 공간을,
"R"은 로봇의 처음 위치를,
"D"는 장애물의 위치를,
"G"는 목표지점을 나타냅니다.

위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.
게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요.
만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

* 제한 사항
- 3 ≤ board의 길이 ≤ 100
- 3 ≤ board의 원소의 길이 ≤ 100
- board의 원소의 길이는 모두 동일합니다.
- 문자열은 ".", "D", "R", "G"로만 구성되어 있으며 각각 빈 공간, 장애물, 로봇의 처음 위치, 목표 지점을 나타냅니다.
- "R"과 "G"는 한 번씩 등장합니다.

 

 

풀이

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<string> board) {
    queue<pair<int, int>> q;
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    int N = board.size(), M = board[0].size();
    int Ex, Ey; // G의 좌표
    vector<vector<int>> count;
    count.assign(N, vector<int>(M, 1000));
    
    // 시작 좌표와 목표 좌표 구하기
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(board[i][j]=='R'){
                q.push({i, j});
                count[i][j] = 0;
            }
            if(board[i][j]=='G'){
                Ex = i;
                Ey = j;
            }
        }
    }
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++){
            int xx = x;
            int yy = y;
            // 장에물 또는 벽에 닿을 때까지 이동
            while(true){
                xx += dx[i];
                yy += dy[i];
                if(xx>=N || xx<0 || yy>=M || yy<0 || board[xx][yy] == 'D'){
                    xx -= dx[i];
                    yy -= dy[i];
                    // 해당 좌표에 도착하는 최소 count를 저장
                    if(count[xx][yy]>count[x][y]+1){
                        count[xx][yy] = count[x][y]+1;
                        q.push({xx,yy});
                    }
                    break;
                }
            }
        }
    }
    
    return count[Ex][Ey]>=1000?-1:count[Ex][Ey];
}

 

해결방법

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

1. count를 저장할 배열에 큰 수 1000를 넣어준다.

2. 시작 위치와 목표 위지를 구한 후, 시작위치의 count를 0으로 설정하고 큐에 넣어준다. 

3. dfs를 사용하여 각 방향별 최단거리를 구한 후, 목표 위치의 카운트에 변함이 없을 경우 목적지까지 도착할 수 없다는 의미이므로 -1을 리턴, 그렇지 않을 경우 목적지의 count를 리턴한다. 

 

// 장에물 또는 벽에 닿을 때까지 이동
while(true){
	xx += dx[i];
	yy += dy[i];
	if(xx>=N || xx<0 || yy>=M || yy<0 || board[xx][yy] == 'D'){
		xx -= dx[i];
		yy -= dy[i];
		// 해당 좌표에 도착하는 최소 count를 저장
		if(count[xx][yy]>count[x][y]+1){
			count[xx][yy] = count[x][y]+1;
			q.push({xx,yy});
		}
		break;
	}
}

 

장애물 또는 벽과 만날 때까지 이동해야 하므로, 멈춘 위치의 count만 반영해 준다. 

 

---

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

프로그래머스