C++ - 아이템 줍기 (BFS)

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

프로그래머스

 

풀긴 풀었지만 쓸데없는 for문을 한 번 더 돌려 그다지 마음에 들지 않는 풀이법입니다.

 

1. 입력대로 사각형을 2차원 배열에 그리면 캐릭터가 디귿 모양으로 움직일 수 없으므로 사각형을 두 배로 크게 키워서 그립니다.

1번 과정만 잘 수행하면 그다음부턴 너비 우선 탐색으로 목적지까지 찾아가면 됩니다.

 

#pragma warning(disable:4996)
#include <stdio.h>
#include <vector>
#include<algorithm>
using namespace std;
int map[110][110], freq[110][110];
int que[3][51 * 51], front, rear;
int dir[2][4] = { {0,1,0,-1},{1,0,-1,0} };

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
	int answer = 0;
	int x1, y1, x2, y2;
	for (int i = 0; i < (int)rectangle.size(); i++)
	{
		x1 = rectangle[i][1]; x2 = rectangle[i][3];
		y1 = rectangle[i][0]; y2 = rectangle[i][2];
		for (int x = x1 * 2; x <= x2 * 2; x++) // 사각형을 두 배로 크게 만듦
			for (int y = y1 * 2; y <= y2 * 2; y++)
				map[x][y] = 1;
	}
    
    // 가장 마음에 들지 않았던 부분
	for (int i = 0; i < (int)rectangle.size(); i++)
	{
		x1 = rectangle[i][1]; x2 = rectangle[i][3];
		y1 = rectangle[i][0]; y2 = rectangle[i][2];
		for (int x = x1 * 2 + 1; x < x2 * 2; x++) // 입력된 사각형의 내부를 0으로 채웁니다.
			for (int y = y1 * 2 + 1; y < y2 * 2; y++)
				map[x][y] = 0;

	}
	
    // BFS 시작
	front = rear = -1;
	que[0][++rear] = characterY * 2;
	que[1][rear] = characterX * 2;
	que[2][rear] = 0;
	freq[que[0][rear]][que[1][rear]] = 1;
	while (front != rear)
	{
		x1 = que[0][++front];
		y1 = que[1][front];
		if(x1 == itemY * 2 && y1 == itemX * 2)
			return que[2][front] / 2; // 사각형의 크기가 두 배이기 때문에 2로 나누어 줍니다.
		for (int i = 0; i < 4; i++)
		{
			if (x1 + dir[0][i] < 1 || x1 + dir[0][i] > 100 || y1 + dir[1][i] < 1 || y1 + dir[1][i] > 100) 
            			continue;
			if (freq[x1 + dir[0][i]][y1 + dir[1][i]] || !map[x1 + dir[0][i]][y1 + dir[1][i]]) continue;

			freq[x1 + dir[0][i]][y1 + dir[1][i]] = 1;
			que[0][++rear] = x1 + dir[0][i];
			que[1][rear] = y1 + dir[1][i];
			que[2][rear] = que[2][front] + 1;
		}
	}
	return que[2][front] / 2;
}