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

프로그래머스

 

📄 문제

리코쳇 로봇이라는 보드게임이 있습니다.

이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.

이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.

다음은 보드게임판을 나타낸 예시입니다.

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

여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.
위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.

게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

 

 

📝 풀이

#include <string>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;

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

int solution(vector<string> board) {
	int width = board[0].size();
	int height = board.size();

	// 큐
	stack<pair<int, int>> q;

	// 거리를 저장
	vector<vector<int>> v(vector<vector<int>>(height, vector<int>(width, 999)));

	// 시작, 도착 지점 저장
	pair<int, int> start{ -1, -1 }, end{ -1, -1 };
	for (int i = 0; i < height; ++i)
		if (start.first != -1 && end.first != -1)
			break;
		else
			for (int j = 0; j < width; ++j)
				if (board[i][j] == 'R')
					start = { i, j };
				else if (board[i][j] == 'G')
					end = { i, j };

	q.push(start);
	v[start.first][start.second] = 0;
	while (!q.empty())
	{
		int x = q.top().second;
		int y = q.top().first;
		q.pop();

		// printf("현재위치: %d %d\n", y, x);

		for (int i = 0; i < 4; ++i)
		{
			int xx = x + dx[i];
			int yy = y + dy[i];

			// 상하좌우 방향을 한칸 이상 갈 수 있는지 확인
			if (xx == -1 || yy == -1 || xx == width || yy == height || board[yy][xx] == 'D')
			{
				// printf("%d %d에서 %d %d로 갈 수 없음!\n", y, x, yy, xx);
				continue;
			}

			// 갈 수 있는 방향에서 최대로 이동
			int xxx = x;
			int yyy = y;
			while (true)
			{
				xxx += dx[i];
				yyy += dy[i];

				if (xxx == -1 || yyy == -1 || xxx == width || yyy == height || board[yyy][xxx] == 'D')
				{
					xxx -= dx[i];
					yyy -= dy[i];

					// 기존에 방문한 거리보다 짧은 거리에 도달했다면?
					// 해당 위치를 짧은 거리로 다시 갱신하여 다시 뻗어나가기
					if (v[yyy][xxx] > v[y][x] + 1)
					{
						q.push({ yyy, xxx });
						// printf("%d %d에서 %d %d로 이동!\n", y, x, yyy, xxx);
						v[yyy][xxx] = v[y][x] + 1;
					}

					break;
				}
			}
		}
	}

	return v[end.first][end.second] == 999 ? -1 : v[end.first][end.second];
}

• 스스로 해결하여 더욱 의미 있었던 문제입니다.
• 평범한 최단거리를 찾는 BFS와 비슷했으나, 한번 이동하는 방향으로 최대로 이동해야한다는 차이가 있습니다.
• 가장 중요한점은, 도착하는 위치가 이미 다른 방법에 의해 도착하였더라도, 최단 이동 거리로 도착한 사례가 있다면, 해당 사례로 갱신하여 재계산을 하여 최단 거리를 지속적으로 갱신하여 문제를 해결합니다.

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

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

int solution(vector<string> board) {

    int row = board.size();
    int col = board[0].size();

    pair<int, int> start;
    pair<int, int> end;
    for(int i = 0; i < row; ++i)
        for(int j = 0; j < col; ++j)
            if(board[i][j] == 'R')
                start = {i, j};
            else if(board[i][j] == 'G')
                end = {i, j};

    vector<vector<int>> dist(row, vector<int>(col, -1));
    queue<pair<int, int>> q;

    q.push(start);
    dist[start.first][start.second] = 0;

    while(!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;

        q.pop();

        for(int i = 0; i < 4; ++i)
        {
            int yy = 0;
            int xx = 0;

            while(true)
            {
                int yyy = y + dy[i] * yy;
                int xxx = x + dx[i] * xx;

                if(yyy < 0 || xxx < 0 || yyy >= row || xxx >= col || board[yyy][xxx] == 'D')
                    break;

                ++yy, ++xx;
            }

            yy = y + dy[i] * (yy - 1);
            xx = x + dx[i] * (xx - 1);

            if(dist[yy][xx] != -1)
                continue;

            dist[yy][xx] = dist[y][x] + 1;
            q.push({yy, xx});
        }
    }

    return dist[end.first][end.second];
}

• 프로그래머스 스킬체크에서 나온 문제로, 기존 풀이 방식과 비슷하게 풀되, 큐를 이용한 BFS를 사용할 때에는 최단거리를 갱신할 필요가 없고, D 또는 끝 영역으로 이동할 때 로직을 비슷하게 구성하였습니다.