[Algorithm] Programmers :: 리코쳇 로봇

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

프로그래머스

struct Node
{
    int y;
    int x;
    int count;
};
 
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
bool visited[101][101] = { false };
 
int solution(vector<string> board)
{
    int answer = -1;
 
    int row = board.size();
    int col = board[0].size();
    queue<Node> q;
 
    for (int i = 0; i < row; ++i)
    {
        for (int j = 0; j < col; ++j)
        {
            if (board[i][j] == 'R')
            {
                q.push({ i,j,0 });
                visited[i][j] = true;
                break;
            }
        }
    }
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        int curCount = q.front().count;
        q.pop();
 
        if (board[curY][curX] == 'G') return curCount;
 
        for (int i = 0; i < 4; ++i)
        {
            int tempY = curY;
            int tempX = curX;
 
            while (1)
            {
                int nextY = tempY + dir[i][0];
                int nextX = tempX + dir[i][1];
 
                if (nextY < 0 || nextY >= row || nextX < 0 || nextX >= col || board[nextY][nextX] == 'D')
                {
                    if (visited[tempY][tempX]) break;
 
                    visited[tempY][tempX] = true;
                    q.push({ tempY,tempX,curCount + 1 });
                    break;
                }
                else
                {
                    tempY = nextY;
                    tempX = nextX;
                }
            }
        }
    }
 
    return answer;
}

특정지점에 도달할 수 있는 최소한의 횟수를 구하는 문제이다.

그래서 기본적인 접근은 BFS로 했으며, 이 문제같은 경우는 조건이 하나 더 달려있다.

board의 벽이나 'D'를 만나기 전까지는 계속해서 미끄러지듯이 이동하는 것이다.

미끄러지듯이 이동할 때는 카운팅을 하지않는다. 즉, 멈춰섰을 때 다음움직임을 할때 카운팅을 하면 된다.

 

처음에는 미끄러지듯이 이동하는것도 한칸씩 큐에 넣는식으로 했더니 전체 테스트케이스중에서 3,4개정도 자꾸 틀리길래 시간 좀 많이 소비했다. 테스트케이스들을 찾아서해도 해결이 안되길래 아예 지우고 다시 짰다.

 

생각해보니 미끄러지듯이 이동하는거는 굳이 한칸씩 넣을필요 없이 바로 처리가 가능하며 코드도 훨씬 깔끔하기 때문에 해당방식으로 다시 구현했다.

은근히 이런 유형도 꽤 나오는것 같아서 백준의 비슷한유형의 문제를 더 풀어봐야겠다.