[프로그래머스] 수레 움직이기 (PCCP 기출문제 4번)

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

프로그래머스

프로그래머스 - 수레 움직이기 (PCCP 기출문제 4번)

문제 유형 : 백트래킹, dfs / bfs, 브루트포스

문제 난이도 : Level 3

 

 

문제 설명

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개씩 존재합니다.

 

 

풀이

이 문제는 dfs + 백트래킹으로 문제를 풀 수 있다.

BFS도 가능하지만, 매 번 도착 정보와 위치 정보를 담기에 너무 번거로울  수 있고, 4*4의 크기라서 dfs가 시간초과가 나지도 않는다.

 

dfs를 구현하는 방법)

두 수레 a, b중에서 a가 먼저 움직이고, b가 그 다음으로 움직이도록 한다.

만약 둘 다 도착했다면 배열에 따로 시간을 저장시킨다.

상하좌우로 다음 움직일 곳을 찾아본다. 만약 수레가 도착하면 더 움직이지 않는다.

다음 조건의 위치로는 움직이지 않는다.:

  1. 범위를 벗어난 경우

  2. 이미 방문한 경우

  3. 벽으로 향하는 경우

  4. 먼저 이동하는 a에만 해당: 현재 b가 있는 위치로 가는 경우

  5. 다음 이동하는 b에만 해당: a가 이동할 다음 위치로 가는 경우

다음 위치로 계속 dfs를 해준다.

백트래킹을 위해 현재위치 a의 4가지 이동 * b의 4가지 이동이 끝나면, 현재 위치의 방문처리를 다시 없앤다.

 

 

a = 빨강, b = 파랑의 경우와

a = 파랑, b = 빨강의 경우 두 가지 모두 dfs를 해준다.

 

배열에는 도착하는 시간들이 저장되어 있다. 이 배열 중 가장 작은 값을 반환하면 된다.

아래 그림에서 파란색이 먼저 이동하는 경우를 보면 어떤 식으로 작동할 것인지 대충 감이 올 것이다.

 

코드

C++

#include <bits/stdc++.h>
using namespace std;

int n;
int m;

// 시간 저장하는 배열, maze를 전역변수에 담기 위한 2차원배열 board
vector<int> times;
vector<vector<int>> board;

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

void dfs(pair<int, int> a, pair<int, int> b, int time, pair<int, int> &aEnd, pair<int, int> &bEnd, vector<vector<bool>> &aVisited, vector<vector<bool>> &bVisited)
{
    int ax = a.first;
    int ay = a.second;
    int bx = b.first;
    int by = b.second;
    // 각각 a, b가 도착했는지 여부
    bool aFinished = (ax == aEnd.first) && (ay == aEnd.second);
    bool bFinished = (bx == bEnd.first) && (by == bEnd.second);

    // cout << "a: {" << ax << ", " << ay << "}" << endl;
    // cout << "b: {" << bx << ", " << by << "}" << endl;
    // cout << "time: " << time << endl;

	// 만약 둘다 끝나면, 시간 배열에 저장시키고 탐색 종료.
    if (aFinished && bFinished)
    {
        times.push_back(time);
        return;
    }
	
    // 현재 위치 방문처리
    aVisited[ax][ay] = true;
    bVisited[bx][by] = true;

	// a부터 이동..
    for (int i = 0; i < 4; i++)
    {
        int nax;
        int nay;
        // a 도착하면 그대로, 아니면 이동 시도
        if (aFinished)
        {
            nax = ax;
            nay = ay;
        }
        else
        {
            nax = ax + dx[i];
            nay = ay + dy[i];
            // 범위를 벗어난곳은 가지않음
            if (nax < 0 || nax >= n || nay < 0 || nay >= m)
                continue;
            // 방문한 적 있으면 가지않음.
            if (aVisited[nax][nay])
                continue;
            // 벽으로 가지않음.
            if (board[nax][nay] == 5)
                continue;
            // 현재 b가 있는곳으로 가지 않음.
            if (nax == bx && nay == by)
                continue;
        }

		// b부터 이동 시도..
        for (int j = 0; j < 4; j++)
        {
            int nbx;
            int nby;
            // b도착하면 그대로, 아니라면 이동 시도
            if (bFinished)
            {
                nbx = bx;
                nby = by;
            }
            else
            {
                nbx = bx + dx[j];
                nby = by + dy[j];
                // 범위를 벗어나면 가지않음
                if (nbx < 0 || nbx >= n || nby < 0 || nby >= m)
                    continue;
                // 방문한 곳은 가지않음
                if (bVisited[nbx][nby])
                    continue;
                // 벽으로 가지않음
                if (board[nbx][nby] == 5)
                    continue;
                // 같은 장소에는 갈 수 없음
                if (nax == nbx && nay == nby)
                    continue;
            }

			// 계속 깊은 곳으로 탐색..(시간은 1 증가한 채로)
            dfs({nax, nay}, {nbx, nby}, time + 1, aEnd, bEnd, aVisited, bVisited);
        }
    }
    // 백트래킹을 위한 방문 처리 해제
    aVisited[ax][ay] = false;
    bVisited[bx][by] = false;
}

int solution(vector<vector<int>> maze)
{
    n = maze.size();
    m = maze[0].size();

    pair<int, int> rStart;
    pair<int, int> rEnd;
    pair<int, int> bStart;
    pair<int, int> bEnd;

    vector<vector<bool>> rVisited;
    vector<vector<bool>> bVisited;
    board.resize(n, vector<int>(m));

	// 시작, 종료위치 파악
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (maze[i][j] == 1)
            {
                rStart = {i, j};
            }
            else if (maze[i][j] == 2)
            {
                bStart = {i, j};
            }
            else if (maze[i][j] == 3)
            {
                rEnd = {i, j};
            }
            else if (maze[i][j] == 4)
            {
                bEnd = {i, j};
            }
            board[i][j] = maze[i][j];
        }
    }

	// 방문여부 초기화 및 레드-블루순으로 탐색 시작..
    rVisited.resize(n, vector<bool>(m, false));
    bVisited.resize(n, vector<bool>(m, false));
    dfs(rStart, bStart, 0, rEnd, bEnd, rVisited, bVisited);
    
    // 방문여부 초기화 및 블루-레드순으로 탐색 시작..
    rVisited.resize(n, vector<bool>(m, false));
    bVisited.resize(n, vector<bool>(m, false));
    dfs(bStart, rStart, 0, bEnd, rEnd, bVisited, rVisited);

	// 만약 도착한 시간이 없다면, 0반환
    if (times.size() == 0)
        return 0;
    // 가장 빠른시간 반환
    return *min_element(times.begin(), times.end());
}