[C++][Programmers][BFS/DFS] 아이템 줍기

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

프로그래머스

---

*문제 설명

직사각형들이 x,y 좌표에 놓여 있을 때, 캐릭터가 가장자리만 이동하면서 아이템이 있는 위치까지 최단 거리를 알아내는 문제이다. 두 사각형이 꼭지점에서 만나나거나 변이 겹치거나 아얘 분리되거나 완전히 포함되는 경우는 없다.

 

*문제예시

문제 입출력 예시

문제 입력은 rectangle의 시작/끝 x,y 좌표가 담긴 배열과 캐릭터의 x,y좌표, 아이템의 x,y 좌표 값이 주어진다.

결과값으로 최단거리를 리턴하면 된다. 

입출력 예시 1,2,3 번 답

입출력 예시의 1,2,3 번 답은 위와 같다. 빨간색이 캐릭터 위치, 파란색이 아이템 위치이다. 빨간색 캐릭터지점에서 파란색 아이템 지점까지의 최단거리는 왼쪽으로 가던, 오른쪽으로 가던 가장 짧은 한가지 경우이다.

 

*풀이방법

1) 우선 board 를 하나 만들어서 주어진 직사각형들을 board에 놓는 작업이 필요하다. board에 놓여있다고 표현하기 위해 1을 넣어준다.

2) 모든 직사각형을 놓았으면 직사각형 내부를 0으로 바꿔준다.

3) 캐릭터 위치에서 시작해서 아이템 위치에 도달할 때까지 BFS 탐색을 진행한다.

 

1) 2) 3) 방법을 머리속으로는 되나 코드로 옮기기 쉽지 않았다. 와중에 검색해서 찾아보니 모든 좌표값들을 2배처리하여 겹치는 부분을 해결해야 한다고 한다.

 

손으로 그려보니 이해가 갔다. 동그라미 친 부분이 위아래 같은 부분인데 위 좌표계와 달리 완전히 겹쳐서 정확한 탐색이 불가 했다. 또, x,y 좌표계를 board에 행열로 표현하니 x,y 좌표가 반대라서  x,y 값을 반대로 넣어주었다.

 

*알아둘것

1) queue의 emplace 함수

- C++ 11에서 처음 추가되었다.

- queue나 map에 값을 넣을 때 make_pair나 make_tuple을 이용하지 않고 emplace 함수로 간단하게 추가할 수 있다.

- push와 달리 바로 오브젝트를 생성하면서 넣기에 copy & move 연산을 따로 수행하지 않아 연산비용이 적다고 한다.

 

*코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int BFS(vector<vector<int>> board, int characterX, int characterY, int itemX, int itemY){    
    int direction[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};
    queue<pair<int,int>> q;
    
    q.emplace(characterY, characterX);
    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        
        if(y == itemY && x == itemX) {
            break;
        }
        for(int i = 0; i < 4; i++){
            int nextY = y + direction[i][1];
            int nextX = x + direction[i][0];
            
            //좌표 범위체크
            if(nextX < 0 || nextX >= board.size() || nextY < 0 || nextY >= board[0].size()) continue;            
            //방문안했으면
            if(board[nextY][nextX] == 1){
                q.emplace(nextY, nextX);
                //1추가해서 방문체크겸 이동거리 저장
                board[nextY][nextX] = board[y][x] + 1;
            }
        }
    }
    return board[itemY][itemX] / 2;
}

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;
    // 101*101 크기의 보드 생성
    vector<vector<int>> board(101, vector<int>(101));
    // 직사각형의 시작과 끝 좌표
    int x1, y1, x2, y2;
    
    // 직사각형들을 board 배열에 놓기
    for(int i = 0; i < rectangle.size(); i++){
        for(int j = 0; j < rectangle[i].size(); j++){
            rectangle[i][j] = rectangle[i][j] * 2;
        }
        x1 = rectangle[i][0], y1 = rectangle[i][1];
        x2 = rectangle[i][2], y2 = rectangle[i][3];
        
        // 좌표값이라 행열로 따지면 x가 열이고 y가 행이라서 반대로 만들어준다.
        for(int y = y1; y <= y2; y++){
            for(int x = x1; x <= x2; x++){
                board[y][x] = 1;
            }
        }
    }
    
    // 직사각형 내부를 0으로 채우기
    for(int i = 0; i < rectangle.size(); i++){
        x1 = rectangle[i][0], y1 = rectangle[i][1];
        x2 = rectangle[i][2], y2 = rectangle[i][3];
        
        for(int y = y1 + 1; y < y2; y++){
            for(int x = x1 + 1; x < x2; x++){
                board[y][x] = 0;
            }
        }
    }
    
    // BFS로 캐릭터 좌표부터 아이템 좌표까지의 최단거리 탐색
    answer = BFS(board, characterX, characterY, itemX, itemY);
    
    return answer;
}