프로그래머스 리코쳇 로봇 [Lv. 2] (C++)

프로그래머스

로봇의 위치를 목표지점까지 옮기는 게임입니다. 로봇을 목표 지점까지 옮기는 가장 적은 비용을 찾아주세요.

(로봇을 이동시킬 때는 벽이나, 장애물에 닿을 때까지 이동해야 합니다.)

 

 

풀이 방법

DFS를 이용해서 풀이합니다. 좌,우로 이동하는 경우와 위,아래로 이동하는 모든 경우의 수를 탐색해줍니다.

// (좌 우 위 아래) 4방향 탐색
for (int i = 0; i < 4; i++)
{
    int ny = y;
    int nx = x;

	// while문 이용하여 이동이 가능한 위치 찾기
    while(ny + dy[i] < board.size() && ny + dy[i] >= 0 &&
          nx + dx[i] < board[0].size() && nx + dx[i] >= 0 &&
         board[ny + dy[i]][nx + dx[i]] != 'D')
    {            
        ny += dy[i];
        nx += dx[i];
    }

	// 현재 방향으로 로봇이 이동할 수 있다면 재귀 호출
    if (ny != y || nx != x)
        DFS(board, ny, nx, cost + 1); 
}

 

 

단순히 DFS만 사용하면 시간 초과가 발생할 수 있기에 dp 기법을 사용하여 중복된 함수 호출을 줄여줍니다.

vector<vector<int>> costs;
void DFS(vector<string>& board, int y, int x, int cost)
{
    if (costs[y][x] <= cost)
        return;  
        
    costs[y][x] = cost;

 

 

정답 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

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

vector<vector<int>> costs;
void DFS(vector<string>& board, int y, int x, int cost)
{
    if (costs[y][x] <= cost)
        return;  
    costs[y][x] = cost;
    
    for (int i = 0; i < 4; i++)
    {
        int ny = y;
        int nx = x;
        
        while(ny + dy[i] < board.size() && ny + dy[i] >= 0 &&
              nx + dx[i] < board[0].size() && nx + dx[i] >= 0 &&
             board[ny + dy[i]][nx + dx[i]] != 'D')
        {            
            ny += dy[i];
            nx += dx[i];
        }
        
        if (ny != y || nx != x)
            DFS(board, ny, nx, cost + 1); 
    }
}

int solution(vector<string> board) {
    
    int MAX = 10000000;
    costs.resize(board.size(), vector<int>(board[0].size(), MAX));
    
    int sy, sx, gy, gx;
    for (int i = 0; i < board.size(); i++)
    {
        for (int j = 0; j < board[i].size(); j++)
        {
            if (board[i][j] == 'R')
            {
                sy = i;
                sx = j;
            }
            
            if (board[i][j] == 'G')
            {
                gy = i;
                gx = j;
            }
        }
    }

    DFS(board, sy, sx, 0);
    return costs[gy][gx] == MAX ? -1 : costs[gy][gx];
}