[프로그래머스/C++]Lv.3 아이템 줍기(BFS, 달팽이알고리즘)

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

프로그래머스

소스코드

배열을 2배해줘야 하는 게 핵심인 것 같다.

배열을 그냥 했을 경우 1이 겹치는 문제가 있어서 해결하기 어려움이 있다.

왼쪽이 기본배열, 오른쪽 2배 배열

소스코드

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

class Pos
{
public:
	Pos(int y, int x) : Y(y), X(x)
	{
	}
public:
	int Y;
	int X;
};

bool CanGo(int minX, int minY, int maxX, int maxY, int nextX, int nextY)
{
	if (nextX < minX || nextX > maxX)
		return false;

	if (nextY < minY || nextY > maxY)
		return false;

	return true;
}

void View(vector<vector<int>> board)
{
	for (int i = 0; i < board.size(); i++)
	{
		for (int j = 0; j < board[0].size(); j++)
		{
			cout << board[i][j];
		}
		cout << endl;
	}
}

int BFS(vector<vector<int>> board, Pos start, Pos dest)
{
	int answer = 0;

	queue<Pos> q;
	vector<vector<bool>> visited{ 101, vector<bool>(101, false) };
	vector<vector<int>> disted{ 101, vector<int>(101, 0) };
	vector<int> dy = { 0, 1, 0, -1 };
	vector<int> dx = { 1, 0, -1, 0 };

	q.push(start);
	visited[start.Y ][start.X ] = true;

	while (q.empty() == false)
	{
		Pos now = q.front();
		q.pop();

		if (now.Y == dest.Y  && now.X == dest.X )
		{
			answer = disted[dest.Y][dest.X] / 2;
			break;
		}

		for (int i = 0; i < 4; i++)
		{
			int nextY = now.Y + dy[i];
			int nextX = now.X + dx[i];

			if (nextX < 0 || nextX >= 101)
				continue;
			if (nextY < 0 || nextY >= 101)
				continue;

			if (visited[nextY][nextX] == 1)
				continue;

			if (board[nextY][nextX] == 0)
				continue;

			q.push(Pos(nextY, nextX));
			visited[nextY][nextX] = 1;
			disted[nextY][nextX] = disted[now.Y][now.X] + 1;

		}
	}
	return answer;
}

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {

	vector<vector<int>> board{ 101, vector<int>(101, 0) };

	//step1 -> 직사각형 테두리들만 1로만든다. 달팽이 알고리즘 사용
	vector<int> dy = { 0, 1, 0, -1 };
	vector<int> dx = { 1, 0, -1, 0 };

	for (int i = 0; i < rectangle.size(); i++)
	{
		int minX = rectangle[i][0] * 2;
		int minY = rectangle[i][1] * 2;
		int maxX = rectangle[i][2] * 2;
		int maxY = rectangle[i][3] * 2;

		int nowX = minX;
		int nowY = minY;

		board[nowY][nowX] = 1;

		int dir = 0;

		int count = 0;
		while (true)
		{
			if (count == 4)
				break;

			int nextX = nowX + dx[dir];
			int nextY = nowY + dy[dir];

			if (CanGo(minX, minY, maxX, maxY, nextX, nextY))
			{
				board[nextY][nextX] = 1;
				nowX = nextX;
				nowY = nextY;
			}
			else
			{
				dir = (dir + 1) % 4;
				count++;
			}
		}
	}
	//////step2 -> 직사각형의 내부를 다시 0으로 밀어준다.
	for (int i = 0; i < rectangle.size(); i++)
	{
		int minX = rectangle[i][0]*2;
		int minY = rectangle[i][1]*2;
		int maxX = rectangle[i][2]*2;
		int maxY = rectangle[i][3]*2;
		for (int y = minY + 1; y < maxY; y++)
			for (int x = minX + 1; x < maxX; x++)
			{
				{
					board[y][x] = 0;
				}
			}
	}

	//확인용) 배열 전체 출력 
	//View(board);

	Pos characterPos(characterY * 2, characterX * 2);
	Pos itemPos(itemY * 2, itemX * 2);
	int result = BFS(board, characterPos, itemPos);

	return result;
}