[프로그래머스] 아이템 줍기 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/87694?language=cpp

프로그래머스

 

BFS

서로 어딘가 겹쳐지는 사각형이 1개~4개가 주어진다. 단 꼭짓점이 같거나 변이 겹치는 경우는 없다함

이때 사각형들의 겉 테두리만 길이라는 가정하에 그 길 위에 두점 (캐릭터 위치, 아이템 위치)가 주어지면

캐릭터가 이 겉 테두리만 따라가서 아이템을 얻기까지의 최단거리를 구하는 문제

 

접근방법

https://velog.io/@rtunu12/lv.3-%EC%95%84%EC%9D%B4%ED%85%9C-%EC%A4%8D%EA%B8%B0

칸이 아니라 선이어서 그런지 감이 안와서 다른 블로그 글을 참고해서 풀이했다.

선이라서 필요한 접근법은 점의 위치를 두배로 키워서 생각해야한다는 점이었음

점을 *2 해서 계산한다음, 겉 테두리는 1, 내부는 모두 2로 채운다.

- 이때 겉 테두리를 1로 칠하고 있는데, 2인 칸을 만나면 2(내부)로 냅둔다. (이미 다른 사각형의 내부를 가로지르는 선이기 때문에 그림상으로는 얇은 선 부분에 해당)

- 반대로 2로 칠하고 있는데 이미 그 칸이 1이어도 2(내부)로 덮는다. (이제 그 점은 더이상 테두리가 아니기 때문)

 

이렇게 2차원 배열로 지도에 가장 바깥 테두리를 표시한 다음

BFS로 캐릭터 위치에서 사방으로 이동가능한 점을 큐에 담고 거리를 1칸씩 증가시켜가면서 item을 만날 때 까지 반복하면 된다.

 

그리고 거리를 갱신할 때나 결과를 반환할 때 꼭 2로 나누어줘야 한다.

 

소스코드

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

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    int answer = 1000000;
    int map[101][101] = {0};
	int dx[4] = {1,-1,0,0};
	int dy[4] = {0,0,1,-1};
    // making map
    for(int i = 0 ; i < rectangle.size() ; i++){
        vector<int> dot = rectangle[i];
        int lx = dot[0]*2;
        int ly = dot[1]*2;
        int rx = dot[2]*2;
        int ry = dot[3]*2;
        for(int x = lx ; x <= rx ; x++){
            for(int y = ly; y <= ry ; y++){
                if( (x == lx || x == rx || y == ly || y == ry) && map[x][y] != 2 ) {
                    map[x][y] = 1;
                } else {
                    map[x][y] = 2;
                }
            }
        }
    }
    
    // bfs
    bool visit[101][101] = {false};
    queue<vector<int>> q;
    q.push({characterX*2, characterY*2, 0});
    int ix = itemX*2;
    int iy = itemY*2;
    while(!q.empty()){
        vector<int> now = q.front();
        visit[now[0]][now[1]] = true;
        if(now[0] == ix && now[1] == iy){
            if(answer > now[2]/2){
                answer = now[2]/2;
            }
        }
        q.pop();
        for(int i = 0 ; i < 4 ; i++){
            int nx = now[0]+dx[i];
            int ny = now[1]+dy[i];
            if(nx >= 0 && ny >= 0 && nx <= 100 && ny <= 100 && map[nx][ny] == 1 && !visit[nx][ny]){
                q.push({nx,ny,now[2]+1});
            }
        }   
    }
    
    return answer;
}