[Programmers] 수레 움직이기 [C++]

문제 설명

n x m 크기 격자 모양의 퍼즐판이 주어집니다.

퍼즐판에는 빨간색 수레와 파란색 수레가 하나씩 존재합니다. 각 수레들은 자신의 시작 칸에서부터 자신의 도착 칸까지 이동해야 합니다.

모든 수레들을 각자의 도착 칸으로 이동시키면 퍼즐을 풀 수 있습니다.

당신은 각 턴마다 반드시 모든 수레를 상하좌우로 인접한 칸 중 한 칸으로 움직여야 합니다. 단, 수레를 움직일 때는 아래와 같은 규칙이 있습니다.

• 수레는 벽이나 격자 판 밖으로 움직일 수 없습니다.
• 수레는 자신이 방문했던 칸으로 움직일 수 없습니다.
• 자신의 도착 칸에 위치한 수레는 움직이지 않습니다. 계속 해당 칸에 고정해 놓아야 합니다.
• 동시에 두 수레를 같은 칸으로 움직일 수 없습니다.
• 수레끼리 자리를 바꾸며 움직일 수 없습니다.

예를 들어, 아래 그림처럼 n = 3, m = 2인 퍼즐판이 있습니다.

• 속이 빨간색인 원은 빨간색 수레를 나타냅니다.
• 속이 파란색인 원은 파란색 수레를 나타냅니다.
• 테두리가 빨간색인 원은 빨간색 수레의 도착 칸을 나타냅니다.
• 테두리가 파란색인 원은 파란색 수레의 도착 칸을 나타냅니다.

위 퍼즐판은 아래와 같은 순서로 3턴만에 풀 수 있습니다.

• 빨간색 사선이 처진 칸은 빨간색 수레가 방문했던 칸을 나타냅니다. 규칙에 따라 빨간색 수레는 빨간색 사선이 처진 칸(방문했던 칸)으로는 이동할 수 없습니다.
• 파란색 사선이 처진 칸은 파란색 수레가 방문했던 칸을 나타냅니다. 규칙에 따라 파란색 수레는 파란색 사선이 처진 칸(방문했던 칸)으로는 이동할 수 없습니다.

퍼즐판의 정보를 나타내는 2차원 정수 배열 maze가 매개변수로 주어집니다. 퍼즐을 푸는데 필요한 턴의 최솟값을 return 하도록 solution 함수를 완성해 주세요. 퍼즐을 풀 수 없는 경우 0을 return 해주세요.

---

제한사항

• 1 ≤ maze의 길이 (= 세로 길이) ≤ 4
  • 1 ≤ maze[i]의 길이 (= 가로 길이) ≤ 4
  • maze[i][j]는 0,1,2,3,4,5 중 하나의 값을 갖습니다.
  maze[i][j] 의미

  0	빈칸
  1	빨간 수레의 시작 칸
  2	파란 수레의 시작 칸
  3	빨간 수레의 도착 칸
  4	파란 수레의 도착 칸
  5	벽

  • 빨간 수레의 시작 칸, 빨간 수레의 도착 칸, 파란 수레의 시작 칸, 파란 수레의 도착 칸은 퍼즐판에 1개씩 존재합니다.

---

입출력 예

maze                                                                                                                                                                        result

[[1, 4], [0, 0], [2, 3]]	3
[[1, 0, 2], [0, 0, 0], [5, 0 ,5], [4, 0, 3]]	7
[[1, 5], [2, 5], [4, 5], [3, 5]]	0
[[4, 1, 2, 3]]	0

---

문제 분석

1. nxm 크기의 격자 모양 퍼즐판에서 빨강, 파랑 수레를 각각 목적지로 최단 턴 수 내에
2. 모든 턴마다 두 수레를 이동해야함 (목적지 도착 경우 제외)
3. 벽 / 격자 밖으로는 이동 불가
4. 방문했던 칸 재방문 불가(색별로)
5. 수래의 두 위치가 동시에 바뀔 수 없다
6. 격자의 크기가 작기 때문에 완전 탐색으로도 가능할 것

---

코드

#include <bits/stdc++.h>
using namespace std;
pair<int,int> RP, BP, RG, BG; // 빨강 시작점, 파랑 시작점, 빨강 목적지, 파랑 목적지
int n, m;
int ans = INT_MAX;
int dy[] = {1,-1,0,0};
int dx[] = {0,0,1,-1};

using namespace std;
bool possible(int x, int y, vector<vector<bool>>& visited, vector<vector<int>>& maze){
	// 좌표에 대한 탐색 가능 여부 분별
    if(x < 0 || y < 0 || x >= n || y >= m) return false;
    if(maze[x][y] == 5) return false;
    if(visited[x][y]) return false;
    return true;
}

void dfs(vector<vector<int>>& maze,
         vector<vector<bool>>& redVisit,
         vector<vector<bool>>& blueVisit,
         pair<int,int> red, pair<int,int> blue, int cnt){ 
         // red = 현재 빨강 좌표, blue = 현재 파랑 좌표

    if(cnt >= ans) return; // 탐색중인 깊이가 이미 구한 답보다 깊어지면 탐색 중단
    if(RG == red && BG == blue){
        ans = min(ans, cnt);
        return;
    }

    for(int i = 0; i<4; i++){
        pair<int,int> nextRed = {red.first + dx[i], red.second + dy[i]}; // 다음 빨강 좌표
        if(red == RG){ // 이미 목적지에 도착 했다면 움직이지 않음
            nextRed = RG;
        }
        else{
            if(!possible(nextRed.first, nextRed.second, redVisit, maze)) continue;
        }

        for(int j = 0; j<4; j++){
            pair<int,int> nextBlue = {blue.first + dx[j], blue.second + dy[j]};
            if(blue == BG){
                nextBlue = BG;
            }
            else{
                if(!possible(nextBlue.first, nextBlue.second, blueVisit, maze)) continue;
            }

            if(nextRed == nextBlue || (red != RG && blue!=BG && red == nextBlue && nextRed == blue)) continue;

            redVisit[nextRed.first][nextRed.second] = true;
            blueVisit[nextBlue.first][nextBlue.second] = true;

            dfs(maze, redVisit, blueVisit, nextRed, nextBlue, cnt + 1);

            redVisit[nextRed.first][nextRed.second] = false;
            blueVisit[nextBlue.first][nextBlue.second] = false;
        }
    }

}
int solution(vector<vector<int>> maze) {

    for(int i = 0; i<maze.size(); i++){
        for(int j = 0; j<maze[i].size(); j++){
            if(maze[i][j] == 1) RP = {i,j};
            else if(maze[i][j] == 2) BP = {i,j};
            else if(maze[i][j] == 3) RG = {i,j};
            else if(maze[i][j] == 4) BG = {i,j};
        }
    }

    n = maze.size(), m = maze[0].size();

    vector<vector<bool>> redVisited(n, vector<bool>(m, false));
    vector<vector<bool>> blueVisited(n, vector<bool>(m, false));

    redVisited[RP.first][RP.second] = true;
    blueVisited[BP.first][BP.second] = true;

    dfs(maze, redVisited, blueVisited, RP, BP, 0);

    return (ans == INT_MAX) ? 0 : ans;
}

• redVisited, blueVisited 를 사용해 두 수레의 각각 방문 격자를 기록했다
• 2중 for문을 통해 빨간색, 파란색에 대해 dfs 를 수행하며, 문제에서 명시된 조건을 위반하는지 확인 했다
• 첫 격자 처리에 유의하자