[프로그래머스] 블록 이동하기 :: c++, 코드, DFS 쓰면 안되는 이유, BFS

블록 이동하기

★★★☆☆ LEVEL 3

문제

블록 이동하기 문제 링크

문제 설명

로봇개발자 무지는 한 달 앞으로 다가온 카카오배 로봇경진대회에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 무지는 0과 1로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 0은 빈칸을 1은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다.

로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이동합니다. 예를 들어, 위 그림에서 오른쪽으로 한 칸 이동한다면 (1, 2), (1, 3) 두 칸을 차지하게 되며, 아래로 이동한다면 (2, 1), (2, 2) 두 칸을 차지하게 됩니다. 로봇이 차지하는 두 칸 중 어느 한 칸이라도 (N, N) 위치에 도착하면 됩니다.

로봇은 다음과 같이 조건에 따라 회전이 가능합니다.

위 그림과 같이 로봇은 90도씩 회전할 수 있습니다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다. 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초 입니다.

0과 1로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성해주세요.

제한사항

• board의 한 변의 길이는 5 이상 100 이하입니다.
• board의 원소는 0 또는 1입니다.
• 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.
• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

---

코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int dirArray[12][4] = { { 0, 1, 0, 1 },{ 1, 0, 1, 0 },{ 0, -1, 0, -1 },{ -1, 0, -1, 0 },{ 1, 1, 0, 0 },{ 0, 0, -1, -1 },{ 0, 0, 1, -1 },{ -1, 1, 0, 0 },{ 1, 1, 0, 0 },{ 0, 0, -1, -1 },{ 1, -1, 0, 0 },{ 0, 0, -1, 1 } };
// 아 => 왼 => 위 => 오 => 가로형 => 세로형
int row;
vector<vector<int>> board;

struct Robot { // 계산 편하게 struct 정의
    int x; int y; int x2; int y2; int time;
    Robot(int a, int b, int c, int d, int e) {
        x = a; y = b; x2 = c; y2 = d; time = e;
    }
};

bool isThereOkay(int r1, int c1, int r2, int c2) {
    // 범위 및 벽 체크
    if (r1<0 || c1<0 || r2<0 || c2<0)
        return false;
    if (r1 > row || r2 > row || c1 > row || c2 > row)
        return false;
    if (board[r1][c1] == 1 || board[r2][c2] == 1)
        return false;
    return true;
}

vector<int> whereCanIGo(Robot& pos) {
    vector<int> candidate;

    for (int i = 0; i<4; i++) {
        pos.x += dirArray[i][0];
        pos.y += dirArray[i][1];
        pos.x2 += dirArray[i][0];
        pos.y2 += dirArray[i][1];
        if (isThereOkay(pos.x, pos.y, pos.x2, pos.y2)) {
            candidate.push_back(i);
            if (pos.x == pos.x2) { // 가로 배치일 때
                if (i == 1) {
                    // 아래쪽으로 이동 가능하면 4, 6번의 회전도 가능
                    candidate.push_back(4);
                    candidate.push_back(6);
                }
                if (i == 3) {
                    // 위쪽으로 이동 가능하면 5, 7번의 회전도 가능
                    candidate.push_back(5);
                    candidate.push_back(7);
                }
            }
            else if (pos.y== pos.y2) { // 세로 배치
                if (i == 0) {
                    candidate.push_back(8);
                    candidate.push_back(11);
                }
                if (i == 2) {
                    candidate.push_back(9);
                    candidate.push_back(10);
                }
            }
        }
        pos.x -= dirArray[i][0];
        pos.y -= dirArray[i][1];
        pos.x2 -= dirArray[i][0];
        pos.y2 -= dirArray[i][1];
    }
    return candidate;
}


string makeKey(int ax, int ay, int bx, int by) {
    if (ax > bx || (ax == bx && ay > by)) {
        int tmp = ax;
        int tmp2 = ay;
        ax = bx; ay = by;
        bx = tmp; by = tmp2;
    }
    return to_string(ax) + "/" + to_string(ay) + "//" + to_string(bx) + "/" + to_string(by);
}

int solution(vector<vector<int>> board2) {
    int answer = 1e8;
    board = board2; // 전역 변수로 사용
    row = board.size() - 1; // 전역 변수로 사용

    vector<string> visited;

    queue<Robot> q;
    Robot* first = new Robot(0, 0, 0, 1, 0);
    q.push(*first); // 첫 위치 저장
    visited.push_back(makeKey(0, 0, 0, 1)); // 첫 위치 방문 기록

    while (q.size()) {
        auto a = q.front(); q.pop(); // queue에 담긴 위치를 하나씩 빼면서

        if ((a.x == row && a.y == row) || (a.x2 == row && a.y2 == row)) { // 도착했을 때
            answer = a.time;
            break;
        }

        vector<int> candidate = whereCanIGo(a); // 현재 위치에서 이동할 수 있는 곳의 정보 받아오기

        while(candidate.size()){
            int idx = candidate.back(); candidate.pop_back();

            int r1 = a.x + dirArray[idx][0];
            int c1 = a.y + dirArray[idx][1];
            int r2 = a.x2 + dirArray[idx][2];
            int c2 = a.y2 + dirArray[idx][3];

            if (r1 > r2 || (r1 == r2 && c1 > c2)) { // r1, c1이 작게 유지
                int tmp = r1; int tmp2 = c1;
                r1 = r2; c1 = c2;
                r2 = tmp; c2 = tmp2;
            }

            if (find(visited.begin(), visited.end(), makeKey(r1, c1, r2, c2)) != visited.end())
                // 이미 방문했던 곳이면 뛰어넘기
                continue;

            visited.push_back(makeKey(r1, c1, r2, c2)); // 위치 방문 기록
            Robot* tmp = new Robot(r1, c1, r2, c2, a.time + 1);
            q.push(*tmp); // 다음 위치 저장
        }
    }


    return answer;
}

풀이

이전 문제와 비슷한 맥락으로 읽어서, 각 위치에서 마지막 도착 구간까지 가는 최소 경로를 저장해두고 이용하는 DP 문제로 풀려고 했다. 입력값도 10^2 이하로 그다지 크지 않았으므로 n^4까지는 가능하다. DFS로 재귀를 돌면서 이미 방문한 곳이면 저장해둔 정보를 쓰는 것으로 생각하고 문제를 풀었다.

하지만 DFS로 풀면 계속 테스트케이스 6번부터 틀렸다고 나온다. 그래서 조건을 똑같이 하고 BFS로 바꾸어 풀었더니 통과였다.

풀이 방식은 다음과 같다.

• queue에 다음 이동할 수 있는 위치들을 넣는다.

  • 이동할 수 있는 위치는 whereCanIGo 함수가 판단하여 넘겨준다.

  • 미리 정의해둔 direction 배열을 이용한다.

  • direction에는 더해주어야할 숫자들이 들어가 있으며, 각 index를 그림으로 표현하면 다음과 같다.

•  

  • 중간에 가로 배치일 때, 세로 배치일 때를 나누어둔 것은 회전을 고려하기 위해서이다.

    • 예를 들어, 1번의 이동(아래로의 이동)이 가능하면 아래 방향으로의 회전도 가능하다.

    • 따라서, 가로방향일 때 i가 1이면 4와 6도 함께 후보에 넣어주는 것이다.

• 이동할 수 있는 위치들을 하나씩 반영하면서 방문 및 시간을 기록한다.

  • 방문 여부는 visited 배열에 string의 형태로 저장하였다.
  • string은 makeKey 함수가 만들어 주며, 주어진 좌표를 이용해서 key를 생성해준다.
  • 해당 키는 위치에 대해 unique하며 이를 보장하기 위해 키를 생성하기 전 정렬을 해준다.

• 마지막 위치에 도달하였다면 다음 경로를 살펴보기를 그만두고 답을 낸다.

최단경로 문제에서 DFS보다 BFS를 쓰는 이유

DFS 코드는 다음과 같다.

---

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int row = 0; int col = 0;
vector<vector<int>> board;
map<string, int> memo;

int direction[12][4] = { {1, 0, 1, 0}, {0, -1, 0, -1}, {-1, 0, -1, 0}, {0, 1, 0, 1}, {1, 1, 0, 0}, {0, 0, -1, -1}, {0, 0, 1, -1}, {-1, 1, 0, 0},{ 1, 1, 0, 0 },{ 0, 0, -1, -1 },{ 1, -1, 0, 0 },{ 0, 0, -1, 1 } };
// 아 => 왼 => 위 => 오 => 가로형 => 세로형


bool compare(pair<int, int> p1, pair<int, int> p2) {
    // ... 위와 같음
}
bool isThereOkay(vector<pair<int, int>> pos) {
    // ... 위와 같음
}

vector<int> whereCanIGo(vector<pair<int, int>>& pos) {
    // ... 위와 같음
}

string makeKey(int ax, int ay, int bx, int by) {
    // ... 위와 같음
}

int leastMove(vector<pair<int, int>>& pos) {
    if ((pos[0].first == row && pos[0].second == col) | (pos[1].first == row && pos[1].second == col))
        return 0;

    vector<int> candidate = whereCanIGo(pos);
    int max = 1e8;

    if (candidate.size() == 0)
        return 1e8;

    while (candidate.size()) {
        int idx = candidate.back(); candidate.pop_back();
        int tmp_ans = 0;

        vector<pair<int, int>> next_pos;
        next_pos.push_back(make_pair(pos[0].first + direction[idx][0], pos[0].second + direction[idx][1]));
        next_pos.push_back(make_pair(pos[1].first + direction[idx][2], pos[1].second + direction[idx][3]));
        sort(next_pos.begin(), next_pos.end(), compare);
        string key_str = makeKey(next_pos[0].first, next_pos[0].second, next_pos[1].first, next_pos[1].second);
        if (memo.find(key_str)!=memo.end())
            tmp_ans += memo[key_str];
        else {
            memo[key_str] = 1e8; // 같은 위치 방문하지 않도록 하기
            int ret = leastMove(next_pos);
            memo[key_str] = ret; tmp_ans += ret;
        }

        if (max>tmp_ans)
            max = tmp_ans;
    }
    return max+1;
}

int solution(vector<vector<int>> board2) {
    int answer = 0;
    row = board2.size()-1;
    col = board2[0].size()-1;
    board = board2;

    vector<pair<int, int>> pos;
    pos.push_back(make_pair(0, 0));
    pos.push_back(make_pair(0, 1));
    memo[makeKey(0, 0, 0, 1)] = 1e8;

    answer = leastMove(pos);


    return answer;
}

---

다른 부분이라고 한다면, 재귀로 돌려서 DFS를 수행한 것이다. DFS는 한 경로를 모두 탐색 후 다른 경로를 탐색하기 때문에, 한 경로를 탐색할 때 같은 위치를 방문하지 않도록 하기 위해서 메모이제이션에 가장 큰 값을 넣는 식으로 처리하였다.

 

https://www.acmicpc.net/board/view/27666

위의 링크를 참조해보면, BFS와 DFS 모두 모든 경우의 수를 고려할 수 있지만 BFS는 최단거리를 찾자마자 종료할 수 있기 때문에 최단 경로 문제에서는 주로 BFS를 이용한다고 한다. 해당 문제는 최단 시간을 계산하기만 하면 되는 문제이므로 BFS를 사용하는 것이 더 적합하다.

 

https://allg.tistory.com/30

위의 블로그를 참조해보면, DFS는 최적의 경로가 여러 개 있는 경우에 탐색을 끝내버려야하기 때문에 또다른 경로를 찾을 수 없다. BFS는 해에 도달하였더라도 종료하지 않고, 계속해서 진행 가능하다.

 

예를 들어, 이와 같은 그래프 예제에서 A => B의 경로는 예측할 수 없는 것이다. 본인의 코드에서도 이미 들른 지점은 가장 큰 수 또는 마지막 지점까지의 경로로 표시해버리기 때문에 다른 경로를 찾을 수 없다.

 

채점 결과

시간은 그다지 잘 나온 것 같지 않다.

 

주요 사항

• 이렇게 복잡한 조건이 주어질 때는 struct를 이용하는 것이 더 간편하다.
• 최단 경로를 찾기만 하면 되는 문제에서는 BFS가 유용하다.

 

다른 사람의 풀이

• 방향을 변수로 잡아서 visited를 구현했던데, 그렇게 하면 한 좌표에서 오른쪽 방향인 것과 반대 좌표에서 왼쪽 방향인 것 (결국 똑같은 것)을 어떻게 구분하는 지 의문이다. 그냥 무시하고 여러 번 검사할 생각하고 메모이제이션을 하는 것인가?