[코테] 프로그래머스 - 리코쳇 로봇

1. 문제

• 격자 모양 게임판 위에서 말을 움직이는 게임
• 움직일 때, 게임판의 끝이나 장애물을 만나면 stop
• 멈추기 전까지 몇칸을 옮겼든 움직인 횟수는 1번
• 이런 방식으로 시작 지점에서 골인 지점까지 도달하는데 필요한 최소 움직임 횟수를 구할 것

2. 풀이

• DFS+백트래킹 고려
  ㅡ> 최단거리 구하는데 적합한 방식은 아님 
  ㅡ> 적용해본 결과 종료 조건이 알맞지 않아서인지 시간 초과 (종료 조건이 적절하지 않아 무한 루프 발생 예상)
• 최단거리를 구하는데 적합한 알고리즘인 BFS 고려 
• 큐와 방문 체크를 이용하여 구현
• 방문 가능한 좌표들을 모두 방문하고도 최단거리를 찾지 못하면 -1로 종료하면 되니 문제에 적합

3. 코드

#include <bits/stdc++.h>

using namespace std;

int solution(vector<string> board) {
    int row=board.size(), col=board[0].size();
    vector<vector<bool>> Visited(row,vector<bool>(col,false));
    queue<tuple<int,int,int>> q; //x,y,count
    
    //find start point
    for(int i=0;i<row;i++)
    {
        for(int j=0;j<col;j++)
        {
            if(board[i][j]=='R')
            {
                q.push({j,i,0});
                Visited[i][j]=true;
            }
        }
    }
    int dx[4]={0,0,-1,1};
    int dy[4]={-1,1,0,0};
    
    while(!q.empty())
    {
        auto [x,y,count]=q.front();
        q.pop();
        
        if(board[y][x]=='G')
        {
            return count;
        }
        for(int i=0;i<4;i++)
        {
            int nx=x, ny=y;
            while(nx+dx[i]>=0&&nx+dx[i]<col&&ny+dy[i]>=0&&ny+dy[i]<row&&board[ny+dy[i]][nx+dx[i]]!='D')
            {
                nx+=dx[i];
                ny+=dy[i];
            }
            if(!Visited[ny][nx])
            {
                Visited[ny][nx]=true;
                q.push({nx,ny,count+1});
            }
        }
    }
    return -1;
}

• 방문 체크용 2차원 배열 vector이용하여 선언 및 false로 초기화
• 큐에 x,y 좌표 및 이동 횟수를 저장하기 위해 queue<tuple<int,int,int>> 형태로 선언
• 시작 지점을 찾고 해당 좌표와 이동횟수를 0으로 하여 큐에 삽입 
• dx,dy 배열을 이용해 상하좌우로 차례로 인접 좌표들을 방문하도록 구성
• 큐가 비어 있지 않은 동안은 반복
  • 큐에서 가장 앞의 원소 참조하여 저장 및 삭제
  • 해당 좌표가 목표지점이라면 현재 이동 횟수 반환 및 종료
  • 아니라면 이동 규칙에 따라 범위 내의 좌표를 상하좌우 순으로 차례로 방문 및 큐에 해당 좌표와 이동 횟수 삽입
• 큐가 비어 반복문이 종료되었는데 최단거리를 구하지 못했다면 도달 불가능하므로 -1 반환

---

참고자료

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

프로그래머스