[프로그래머스] 리코쳇 로봇 (C++) (추가예정)

이얀조·2023년 4월 20일

🎀프로그래머스

목록 보기

13/21

🍩 문제 설명

리코쳇 로봇이라는 보드게임이 있습니다.
이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.
이 게임에서 말의 움직임은 상, 하, 좌, 우 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"는 한 번씩 등장합니다.

🏵 풀이

다음과 같은 방법을 기준으로 문제를 해결하고자 하였다.

체크하기 위한 배열을 작성하면서 만약 G 의 4방향이 모두 이동가능한 구간이면 -1을 리턴한다.

BFS 방식을 활용하여 구현한다.
2-1. R의 좌표를 Queue 에 넣고 시작한다. → Queue 에 push 되었기 때문에 ckVec[R].second 를 1로 할당한다.
2-2. 4방향을 돌면서, 이동할 수 없을때 까지 while loop를 돈다.
ex) 방향 : 오른쪽 → 장애물에 부딪힐 때 까지
2-3. 문에서 BFS적인 특성요소를 작성한다.

이후 G에 도달하면 이동횟수를 바로 return 한다.

본인은 2-2, 2-3 에서 많이 애를 먹었다 . .

2-2와 2-3의 설명을 그림으로 잠깐 덧붙이자면 다음과 같다.

문제에서 주어진 예제가 위와 같이 있다.

R에서 시작하므로 Queue 에 R의 좌표와 Push 여부(Queue.second)를 입력해준다.

Queue 에서 front 좌표를 꺼내 방향을 탐색한다.

위의 이미지를 보면 R 을 4 방향으로 탐색했을 때 아래 와 왼쪽 만 이동이 가능하다.
먼저 아래 이동이 가능하기 때문에 while loop로 이동이 불가한 상태까지 이동해야 하지만 이후 이동할 수 없기 때문에 break 된다.

동일하게 왼쪽도 진행한다.

1번째 이동이 지난 후 2번째 이동까지 한 경우이다. 분홍색으로 칠해진 부분은 Queue 에 push 된 좌표이다.

2번째 이동에서도 장애물의 끝까지 while loop가 반복되어야 한다.

따라서 위의 이동이 끝까지 진행되면 아래와 같다.

이미 G에 도착했기 때문에 그 이후는 굳이 탐색하지 않고 return 을 해 주었다.

break 구문이 많아서 아쉬운 문제였다.

그렇다 보니까 조금 복잡하고 긴 코드가 나온 것 같은데 다른 사람 풀이를 보니 매우 쉽게 해결한 사람들도 많이 보였다.

break 조건 부분을 생략하고 다르게 조건을 짤 수 있었다면 더 좋았을 것 같다.

다음에는 Python 으로도 문제를 풀어보고 추가할 예정이다 :>

🌴 코드

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
#include <climits>
#define pii pair<int, int>
#define vii vector<vector<pii> >
using namespace std;

struct DIR {
    int x;
    int y;
};
DIR *dir = new DIR[4];

int solution(vector<string> board) {
    vii ckVec(board.size(), vector<pii>(board[0].size(), make_pair(0, 0)));
    DIR start, goal;
    
    dir[0].y = -1; dir[0].x = 0; //up
    dir[1].y = 0; dir[1].x = 1; //right
    dir[2].y = 1; dir[2].x = 0; //down
    dir[3].y = 0; dir[3].x = -1; //left
    
    // setting start, goal
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[i].size(); j++) {
            if (board[i][j] == 'R') {
                start.x = j;
                start.y = i;
            }
            else if (board[i][j] == 'G') {
                goal.x = j;
                goal.y = i;
                
                // check
                int ck = 0;
                for (int d = 0; d < 4; d++) {
                    if ((j + dir[d].x >= 0 && j + dir[d].x < board[i].size()) && (i + dir[d].y >= 0 && i + dir[d].y < board.size())) {
                        if (board[i + dir[d].y][j + dir[d].x] != 'D') ck += 1;
                    }
                }
                
                if (ck == 4) return -1;
            }
        }
    }
    
    // start bfs
    queue<DIR> q;
    ckVec[start.y][start.x].second = 1;
    q.push(start);
    
    while(!q.empty()) {
        DIR now = q.front();
        q.pop();
        
        for (int d = 0; d < 4; d++) {
            int isGoal = 0;
            DIR next;
            next.y = now.y; next.x = now.x;
            while(true) {
                DIR tmpDir;
                tmpDir.x = next.x + dir[d].x; tmpDir.y = next.y + dir[d].y;
                
                if ((tmpDir.x >= 0 && tmpDir.x < board[0].size()) && (tmpDir.y >= 0 && tmpDir.y < board.size())) {
                    // 다음 좌표가 장애물인 경우 만약 isGoal을 방금 지났다면 answer setting
                    if (board[tmpDir.y][tmpDir.x] == 'D') { 
                        if (isGoal) return ckVec[now.y][now.x].first + 1;
                        
                        // 횟수 setting
                        if (ckVec[next.y][next.x].first != 0 || ckVec[next.y][next.x].second == 1) ckVec[next.y][next.x].first = min(ckVec[now.y][now.x].first + 1, ckVec[next.y][next.x].first);
                        else ckVec[next.y][next.x].first = ckVec[now.y][now.x].first + 1;
                        //push 여부 setting
                        if (ckVec[next.y][next.x].second == 0) {
                            q.push(next);
                            ckVec[next.y][next.x].second = 1;
                        }
                        break;
                    }
                    else {
                        // setting isGoal
                        if (board[tmpDir.y][tmpDir.x] == 'G') isGoal = 1;
                        else isGoal = 0; // isGoal 초기화
                        
                        next.y = tmpDir.y; next.x = tmpDir.x;
                    }
                }
                else {
                    if (isGoal) return ckVec[now.y][now.x].first + 1;
                    
                    // setting ckVec.first(횟수)
                    if (ckVec[next.y][next.x].first != 0 || ckVec[next.y][next.x].second == 1) ckVec[next.y][next.x].first = min(ckVec[now.y][now.x].first + 1, ckVec[next.y][next.x].first);
                    else ckVec[next.y][next.x].first = ckVec[now.y][now.x].first + 1;
                    // setting ckVec.second(push 여부)
                    if (ckVec[next.y][next.x].second == 0) {
                        q.push(next);
                        ckVec[next.y][next.x].second = 1;
                    }
                    break;
                }
            }
        }
    }
    return -1;
}

🍂 어려웠던 점

1. 좌표 접근을 제대로 하지 않은 부분
→ 좌표 접근을 제대로 하지 않아서 계속 Segmentation Err가 발생하였다.
→ 오타 . . 도 조심하자 . . Core Dump 때문에 계속 고생했다 . .
2. 제대로 조건 처리를 하지 않은 부분
→ return -1 이 되는 경우를 미리 처리했다고 생각해서 마지막에 return 을 해주지 않았는데, 다른 조건이 있다는 것을 생각하지 못했다 . .

이얀조

이얀조다!

이전 포스트

[프로그래머스] 크기가 작은 부분 문자열 (C++)

다음 포스트

[프로그래머스] 리코쳇 로봇 (C++) (추가예정)