🌞문제

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

🌞접근법

조건1. 여러 직사각형이 주어지고, 그 직사각형들은 플레이어가 움직일 수 있는 동선이 된다.
조건2. 서로 다른 두 직사각형의 x축 또는 y축 좌표가 같은 경우는 없다.
조건3. 직사각형은 서로의 꼭짓점에서 만날 일이 없다.
조건4. 직사각형의 변이 겹치는 경우도 존재하지 않는다.
조건5. 전체의 모습으로 보면 직사각형들은 떨어져 있는 공간이 없다.
조건6. 하나의 직사각형이 하나의 직사각형 안에 포함되는 경우는 없다.
조건7. rectangle의 세로길이는 1~4
조건8. rectangle은 왼쪽아래 모서리, 오른쪽 위의 모서리의 x,y 좌표를 가지고 있다.
조건9. 모든 좌표값은 1~50
조건10. 캐릭터의 위치는 (50,50) 안에 있다.
조건11. 아이템의 위치는 (50,50) 안에 있다.
조건12. 캐릭터와 아이템이 같은 경우는 없다.

구해야하는 것 : 캐릭터가 아이템을 줍기 위하여 이동해야 하는 가장 짧은 거리를 구하여라.

일단 이 문제의 경우 외곽만 표현이 되는 배열을 만들어 주어야 한다.
이 배열을 만드는 방법은 먼저 직사각형에 해당하는 부분을 2차원 배열에 모두 1로 표현을 하고,
직사각형의 외곽을 제외한 안쪽 부분에 대하여 for문을 돌면서 2차원 배열을 0으로 채워주면 된다.

이렇게 하게되면 외곽 모양만 나타난 배열이 생겨날 것이다.

그런데 이렇게만 하면 문제가 생긴다.

ㄷ자 부근을 ㅁ자로 인식을 하여 지나가지 못하는 부분을 지나가게 된다.
이에 따라서 모든 좌표를 *2를 해주어서 풀어야 한다.

그렇게 해서 외곽만 나타낸 2차원 배열을 구했다면,
캐릭터를 좌표를 시작점으로 하여 나올 수 있는 모든 경우의 수를 BFS를 통해 구하다가,
item 위치에 도착을 하는 경우가 발생하면 결과 값을 return 하면 된다.

🌞풀이

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

using namespace std;

int grid[101][101];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
queue<pair<int,int>> q;
int visit[101][101];

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    characterX *= 2;
    characterY *= 2;
    itemX *= 2;
    itemY *= 2;
    
    for(int i=0; i<rectangle.size();i++)
    {
        for(int j=rectangle[i][1]*2; j<=rectangle[i][3]*2 ; j++)
        {
            for(int k=rectangle[i][0]*2 ;k<=rectangle[i][2]*2;k++)
            {
                grid[j][k] = 1;
            }
        }
    }
    
    for(int i=0; i<rectangle.size();i++)
    {
        for(int j=rectangle[i][1]*2+1; j<=rectangle[i][3]*2-1 ; j++)
        {
            for(int k=rectangle[i][0]*2+1 ;k<=rectangle[i][2]*2-1;k++)
            {
                grid[j][k] = 0;
            }
        }
    }  
    
    
    q.push(make_pair(characterX,characterY));
    visit[characterY][characterX] = 1;
    
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        if(x == itemX && y==itemY)
        {
            return grid[y][x]/2;
        }
        
        for(int i=0;i<4;i++)
        {
            int mx = x + dx[i];
            int my = y + dy[i];
            
            if(mx > -1 && my > -1 && mx<101 && my <101 && grid[my][mx] > 0 && visit[my][mx] == 0)
            {
                q.push(make_pair(mx,my));
                visit[my][mx] = 1;
                grid[my][mx] = grid[y][x] + 1  ;         
                
            }
        }
        
    }

    
}