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

문제 

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

프로그래머스

 

map[51][51] = {-1,} 
visited[51][51] = {0,}
dist [][] // 출발점 ~ 해당좌표까지 거리 
* 변의 길이가 1인 경우 안에 0을 채울 수 없음 그래서 모든 값*2 해줌!

 

0을 채울 수 없는 경우

2배 하면 가능 

 

map[101][101] = {-1,}
 visited[101][101] = {0,}
dist[101][101] = {0, }
1 ) map 에 사각형 선을 1, 그 안을 0 , 그 외를 -1로 채운다. O(1*4*4)=O(1)
for( rectangle.size() 만큼 반복 )
for( ractangle[0].size() 만큼 반복) 
좌표를 확인하고 채운다. 
** 각 좌표를 2배 해준다. 
fillRactangle() 함수 실행

2 ) fillRactangle(int x1, int y1, int x2, int y2 )
for( x1 부터 x2까지 반복 ) - x좌표 채우기 
map[][y1] = 1; 
map[][y2] = 1;
for ( y1 부터 y2 까지 반복 ) 
map[x1][] = 1;
map[x2][] = 1;

//사각형 안 0으로  채우기 
for( y1+1 부터 y2-1까지 반복 )
for( x1+1 부터 x2-1 까지 반복 )
map[x][y] = 0;

3) bfs( 캐릭터 좌표 )
큐에 현재 좌표를 넣는다. 
while( 큐 != 0 )
현재 좌표 = 큐.front 
큐.pop
현재 좌표가 아이템 위치인지 확인 
아이템 위치면 break 
현재 좌표 상하좌우 살핌 
if 1이 있다면 해당좌표 큐에 추가 
   거리배열 +1 

return 거리배열[아이템위치] /2 

 

코드 

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

using namespace std;

int map[105][105]={-1,};
int visited[101][101] = {0,};
int dist[101][101] ={0,};
queue<pair<int,int>> q;

int x[4] = {0,0,1,-1};
int y[4] = {1,-1,0,0};


//사각형 선 : 1 
void fillRactangle(int x1, int y1, int x2, int y2)
{
    for(int i = x1; i<=x2; i++) //세로선 1
    {
        map[i][y1] = 1;
        map[i][y2] = 1;
    }
    for(int i=y1; i<=y2; i++) //가로선 1 
    {
        map[x1][i] = 1;
        map[x2][i] = 1;
        
    }  
}
//사각형 안 0으로 채우기
void fillZero(int x1, int y1, int x2, int y2)
{
    for(int i=y1+1; i<y2; i++) //사각형 안 0으로 채우기
    {
        for(int j=x1+1; j<x2; j++)
        {
            map[j][i] = 0;
        }
    }
}

void bfs(int ch_x, int ch_y, int i_x, int i_y) //캐릭터x,y좌표
{
    visited[ch_x][ch_y]= 1;//방문표시
    q.push(make_pair(ch_x,ch_y));
    dist[ch_x][ch_y] ++; 
    
    while(!q.empty())
    {
        pair<int,int> now = q.front();
        q.pop();
        //아이템 위치까지 왔으면 멈춤 
        if(now.first == i_x & now.second ==i_y)
            break;
        for(int i=0; i<4; i++)
        {
            int py = now.first+y[i];
            int px = now.second +x[i];
            
            if(visited[py][px] == 0 & map[py][px] == 1)
            {
                visited[py][px] = 1;
                q.push(make_pair(py,px));
                dist[py][px] = dist[now.first][now.second]+1;
            }
        }
    }
}

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    //int answer = 0;
    
    for(int i=0; i<rectangle.size(); i++)
    {        
        fillRactangle(rectangle[i][0] *2, rectangle[i][1]*2, rectangle[i][2]*2, rectangle[i][3]*2);
    }
    
    for(int i=0; i<rectangle.size(); i++)
    {
        fillZero(rectangle[i][0] *2, rectangle[i][1]*2, rectangle[i][2]*2, rectangle[i][3]*2);
    }
    
    bfs(characterX*2,characterY*2,itemX*2,itemY*2);
    
    return dist[itemX*2][itemY*2]/2;
}