수레 움직이기 [Lv. 3] (C++)

프로그래머스

N * M 크기 격자 모양의 퍼즐판이 주어질 때 격자 위에 빨간, 파란색 수레가 하나씩 존재합니다.

이 수레를 동시에 한 칸씩 움직일때 목표지점 까지 도달하는 최소 시간을 구하는 문제입니다.

 

풀이 방법

우선 이 문제는 모든 경로에 대해서 탐색할 필요가 있기에 DFS로 풀면 좋습니다.

수레는 모두 한 번에 한칸 씩만 움직일 수 있으며, 두 수레가 위치를 바꾸는 것은 안되고

같은 격자로 이동하는 것도 안됩니다. 또한 이동했던 길로 다시 돌아가는 것도 안됩니다.

 

1. 동시에 두개의 수레를 움직인다.

이 문제에서 많이 해매는 부분이 두 수레가 동시에 움직이는 부분입니다.

동시에 움직일 수 있기에 기차처럼 붙어서 이동하는 것도 가능합니다.

하지만 한번에 한 수레씩 이동하는 코드를 만들었다면 기차처럼 붙어서 이동하는것이 불가능 합니다.

(a가 b의 위치로 갈때 b도 동시에 다른 곳으로 이동한다면 가능, 그렇지 않다면 불가능)

 

이 문제를 해결하기 위해서는 각 수레의 다음 위치를 이중 for문을 이용하여 결정하면 됩니다.

그렇게 되면 각자의 다음 위치를 확인할 수 있기에 if문 체크가 편합니다.

 

2. 방문 배열을 두개를 사용한다.

두 개의 수레의 방문을 체크하는 부분을 두개의 배열을 사용하는게 좋습니다. (pair도 가능)

 

3. 도착한 수레가 있는가

도착한 수레가 있다면 그 수레는 움직이면 안됩니다. 함수에 인자로 넘겨받은 위치값을 그대로 사용하면 되겠습니다.

하나의 수레가 멈춰있더라도 이동 횟수는 똑같이 카운트합니다.

 

정답 코드

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

using namespace std;

// 다음 이동 방향
int dir[4][2] = {
    {1, 0}, {-1, 0}, {0, 1}, {0, -1}
};

// 두 수레의 방문 배열
vector<vector<pair<bool, bool>>> visited;
int answer = 100000000;
bool check(vector<vector<int>>& board, int y, int x)
{  // 범위를 벗어나거나 벽이라면 false return
    return y >= 0 && y < board.size() && x >= 0 && x < board[0].size() && board[y][x] != 5;
}

void DFS(vector<vector<int>>& maze, int ry, int rx, int by, int bx, int cnt)
{
	// 두 수레 모두 도착했다면 종료
    if (maze[ry][rx] == 3 && maze[by][bx] == 4)
    {
        answer = min(answer, cnt);
        return;
    }

    for (int i = 0; i < 4; i++)
    {
        int nry = ry;
        int nrx = rx;
        
        // 수레가 도착하지 않았을 때에만 이동
        if (maze[nry][nrx] != 3)
        {
            nry += dir[i][0];
            nrx += dir[i][1];
            
            // 이동 가능한 곳인지 체크, 방문한 노드인지 체크
            if (!check(maze, nry, nrx) || visited[nry][nrx].first)
                continue;
            
            visited[nry][nrx].first = true;
        }
        
        for (int j = 0; j < 4; j++)
        {
            int nby = by;
            int nbx = bx;
            
            // 수레가 도착하지 않았다면 이동
            if (maze[nby][nbx] != 4)
            {
                nby += dir[j][0];
                nbx += dir[j][1];
                
                if (!check(maze, nby, nbx) || visited[nby][nbx].second)
                    continue;
            
            }
   
            // 같은 곳으로 가거나, 위치를 바꾸는건 안됨
            if ((nry == nby && nrx == nbx) || 
                (nry == by && nrx == bx && nby == ry && nbx == rx))
                continue;

			// 방문 체크, 다른 경로로 가기 위한 방문 체크 취소
            visited[nby][nbx].second = true;
            DFS(maze, nry, nrx, nby, nbx, cnt + 1);
            visited[nby][nbx].second = false;
            
        }
        visited[nry][nrx].first = false;   
    }
}


int solution(vector<vector<int>> maze) {
    visited.resize(maze.size(), vector<pair<bool, bool>>(maze[0].size(), make_pair(false, false)));
    
    // 두 수레의 위치 찾기
    int ry, rx, by, bx;
    for (int i = 0; i < maze.size(); i++)
    {
        for (int j = 0; j < maze[i].size(); j++)
        {
            if (maze[i][j] == 1)
            {
                ry = i;
                rx = j;
            }
            else if (maze[i][j] == 2)
            {
                by = i;
                bx = j;
            }
        }
    }
    // 방문 체크
    visited[ry][rx].first = true;
    visited[by][bx].second = true;
    
    DFS(maze, ry, rx, by, bx, 0);
    
    // 찾지 못했다면 0을 반환 그렇지 않다면 answer반환
    return answer == 100000000 ? 0 : answer;
}