리코쳇 로봇 C++

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

프로그래머스

 

※ 문제

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

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

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

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

 

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

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

 

※ 나의 풀이

이 문제는 그렇게 어렵지 않았다.

BFS 관련 응용 문제이지만 한 칸씩 이동하는 것이 아닌 미끄러져 이동하는 것이다.

미끄러져 이동하는 것은 while문을 이용하여 D를 만나거나 map 끝에 다다르거나 할때 멈추면 된다.

여기에서 주의할 점은 G (목표)를 만난다고 해서 멈출 수 있는게 아니라는 것이다.

 

 

	// 상하좌우
	vector<int> di = { -1, 1, 0, 0 };
	vector<int> dj = { 0, 0, -1, 1 };

	// 맵 바꿔주기 및 시작위치, 종료위치 저장해주기
	vector<vector<char>> map;
	vector<vector<int>> ch_map(board.size(), vector<int>(board[0].size(), 2147000000));
	pair<int, int> S, G;
	vector<char> tmp;
	for (int i = 0; i < board.size(); i++)
	{
		for (int j = 0; j < board[i].size(); j++)
		{
			if (board[i][j] == 'R') S = make_pair(i, j);
			else if (board[i][j] == 'G') G = make_pair(i, j);
			else if (board[i][j] == 'D') ch_map[i][j] = 2146999999;
			tmp.push_back(board[i][j]);
		}
		map.push_back(tmp);
		tmp.clear();
	}
	ch_map[S.first][S.second] = 0;

	// 경로 찾기
	queue<pair<int, int>> q;
	q.push(S);
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		int i = 0;
		int xx, yy;
		for (i = 0; i < 4; i++)
		{
			xx = x;
			yy = y;
			while (1)
			{
				xx += di[i];
				yy += dj[i];
				if (xx < 0 || yy < 0 || xx >= map.size() || yy >= map[0].size()) break;
				if (map[xx][yy] == 'D') break;
			}
			xx -= di[i];
			yy -= dj[i];

			if (ch_map[xx][yy] != 2147000000) continue;
			ch_map[xx][yy] = min(ch_map[xx][yy], ch_map[x][y] + 1);
			q.push(make_pair(xx, yy));
		}
	}

	answer = ch_map[G.first][G.second];