[Programmers] C++ 깊이/너비 우선 탐색(DFS/BFS) - 아이템 줍기

 

[Programmers] C++ 깊이/너비 우선 탐색(DFS/BFS) - 아이템 줍기

 

문제 설명

겹쳐진 다각형 도형의 테두리를 따라서 시작점 ~ 도착점 까지의 최소 거리를 구하는 문제이다.

 

단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없다.

서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없다.

지형이 2개 이상으로 분리된 경우도 없습니다.

한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없다.

 

풀이과정

아무리 머리를 굴려도 마땅한 방법이 생각나지 않았다. 한 문제를 가지고 1시간 가량 고민을 했는데 명쾌한 아이디어가 떠오르지 않아서 구글링을 통해 블로그에 정리를 잘 해주신 분들의 풀이 도움을 받았다.

 

 

| 핵심 아이디어는 모든 변수값에 2배를 해주는 것! |

 

왜 2배를 해주어야 하냐면, 입출력 예시 1번을 통해 이유를 도출해낼 수 있다.

 

예시 1번의 바깥테두리는 노란색으로 칠해진 점 4개를 지나고 있다.

 

`(3,5)`점에서 `(3,6)`으로 가려면 사실은 아래와 같은 절차를 거쳐야 한다.

 

 

하지만 그림상으로 볼 때와는 달리, 이것을 좌표로 나타내게 되면 `(3,5)`점과 `(3,6)` 점은 1 -> 2 -> 3 의 경로가 아니라 바로 직행할 수 있다고 오해하기 쉽다.

 

따라서 지금의 좌표상태 그대로 풀이를 하게 되면 복잡한 로직이 필요해진다.

하지만, 모든 좌표를 2배씩 해주게 되면 `(6, 10)`과 `(6,12)` 점이 되기 때문에 앞선 문제들을 방지할 수 있게 된다.

 

풀이 ( 정답 )

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

using namespace std;

// 상 우 하 좌
int dX[4] = {0, 1, 0, -1};
int dY[4] = {1, 0, -1, 0};

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    int answer = 0;
    
    // 모든 좌표값을 2배 해준다.
    characterX *= 2, characterY *=2, itemX *= 2, itemY *= 2;
    vector<vector<int>> board(110, vector<int>(110, -1));
    
    for(int i = 0; i < rectangle.size(); i++) {
    	// 직사각형 좌표도 2배 해준다.
        for(int j = 0; j < rectangle[i].size(); j++) {
            rectangle[i][j] *= 2;
        }
        int x1 = rectangle[i][0], x2 = rectangle[i][2];
        int y1 = rectangle[i][1], y2 = rectangle[i][3];
        
        // 이미 다른 직사각형의 안쪽부분이라 0으로 할당되었다면,
        // 현재 직사각형의 테두리여도 1로 할당하지 않음.
        for(int y = y1; y <= y2; y++) {
            if(board[x1][y] != 0)
                board[x1][y] = 1;
            if(board[x2][y] != 0)
                board[x2][y] = 1;
        }
        for(int x = x1; x <= x2; x++) {
            if(board[x][y1] != 0)
                board[x][y1] = 1;
            if(board[x][y2] != 0)
                board[x][y2] = 1;
        }
        
        // 직사각형의 안쪽부분을 모두 0으로 할당
        for(int y = y1 + 1; y < y2; y++) {
            for(int x = x1 + 1; x < x2; x++) {
                board[x][y] = 0;
            }
        }
    }
    
    // BFS
    queue<pair<int, int>> q;
    q.push({characterX, characterY});
    while(!q.empty()) {
        auto cur = q.front();
        int x = cur.first;
        int y = cur.second;
        q.pop();
        
        // 도착지이면 break
        if(x == itemX && y == itemY) break;
        
        for(int i = 0; i < 4; i++) {
            if(board[x + dX[i]][y + dY[i]] == 1) {
                q.push({x + dX[i], y + dY[i]});
                board[x + dX[i]][y + dY[i]] = board[x][y] + 1;
            }
        }
    }
    
    // 모든 좌표를 2로 했기 때문에 마지막 answer는 2로 나눈값이 답이 된다.
    answer = board[itemX][itemY] / 2;
    return answer;
}

 

곧 다가올 코딩테스트 제발 화이팅 🔥🔥🔥