[코드트리 기출문제 50] 코드트리 빵

생각해라 생각

https://www.codetree.ai/frequent-problems/codetree-mon-bread/description

코드트리

#include <cstdio>
#include <cstring>
#include <queue>
int N, M;
int board[15 + 2][15 + 2];

struct _st
{
	int px, py;
	int x, y;
	bool arrived;
};
_st People[30 + 2];	// 사람 최대 30명

int cant_go[15 + 2][15 + 2];

struct _qt
{
	int x, y;
	int move;
};
std::queue<_qt> Q;
int visited[15 + 2][15 + 2];


// dir
int dir_x[4] = { -1, 0, 0, 1 };
int dir_y[4] = { 0, -1, 1, 0 };

void input()
{
	scanf("%d %d", &N, &M);
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			scanf("%d", &board[r][c]);
		}
	}
	for (int i = 1; i <= M; i++) {
		int r = 0, c = 0;
		scanf("%d %d", &r, &c);
		People[i] = { r, c, -1, -1, false };	// 각 사람마다 가고싶은 편의점 위치 
	}
} 

int get_dist(int x, int y, int num)
{
	// init
	Q = {};
	memset(visited, 0, sizeof(visited));

	Q.push({ x, y, 0 });
	visited[x][y] = 1;

	while (!Q.empty()) {
		_qt data = Q.front();
		Q.pop();
		
		if (data.x == People[num].px && data.y == People[num].py) return data.move;


		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
			if (visited[nx][ny]) continue;
			if (cant_go[nx][ny]) continue;
			Q.push({ nx, ny, data.move + 1 });
			visited[nx][ny] = 1;
		}
	}
	return -1;
}



void move_people()
{
	for (int i = 1; i <= M; i++) {
		if (People[i].x == -1 && People[i].y == -1) break;	// 격자 공간 안에 안들어옴
		if (People[i].arrived == true) continue;	// 이미 편의점에 도착함

		int curr_x = People[i].x; 
		int curr_y = People[i].y;

		int min_dist = 0x7fffffff;
		int opt_dir = -1;
		
		for (int p = 0; p < 4; p++) {
			int nx = curr_x + dir_x[p];
			int ny = curr_y + dir_y[p];

			if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
			if (cant_go[nx][ny]) continue;
			int dist = get_dist(nx, ny, i);
			if (dist == -1) continue;		// 와.... 이거 넣어줘야지.... 최단거리 갱신 안되는거니까.. 
			if (dist < min_dist) {
				min_dist = dist;
				opt_dir = p;
			}
		}
		People[i].x = curr_x + dir_x[opt_dir];
		People[i].y = curr_y + dir_y[opt_dir];
	}
	//printf("-------move------\n");
	//debug();
}


void is_arrived()
{
	for (int i = 1; i <= M; i++) {
		if (People[i].x == People[i].px && People[i].y == People[i].py) {	// 편의점에 도착했다면 편의점에서 멈춤 
			cant_go[People[i].px][People[i].py] = 1;
			People[i].arrived = true;
		}
	}
}



void go_basecamp(int num)
{
	// init
	Q = {};
	memset(visited, 0, sizeof(visited));
	int min_dist = 0x7fffffff;
	int opt_row = 0x7fffffff;
	int opt_col = 0x7fffffff;


	int goal_x = People[num].px;
	int goal_y = People[num].py;
	Q.push({ goal_x, goal_y, 0 });
	visited[goal_x][goal_y] = 1;


	while (!Q.empty()) {
		_qt data = Q.front();
		Q.pop();

		if (min_dist < data.move) break;

		if (board[data.x][data.y] == 1) {
			if ((min_dist > data.move) ||
				(min_dist == data.move && opt_row > data.x) ||
				(min_dist == data.move && opt_row == data.x && opt_col > data.y)) {
				min_dist = data.move;
				opt_row = data.x;
				opt_col = data.y;
			}
			continue;
		}

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
			if (cant_go[nx][ny]) continue;
			if (visited[nx][ny]) continue;
			Q.push({ nx ,ny, data.move +1 });
			visited[nx][ny] = 1;
		}
	}
	People[num].x = opt_row;
	People[num].y = opt_col;
	cant_go[opt_row][opt_col] = 1;
	//printf("time: %d, go bc\n", num);
	//debug();
}


bool chk_all()
{
	for (int i = 1; i <= M; i++) {
		if (People[i].arrived == false) return false;
	}
	return true;
}


int simulation()
{
	int time = 1;
	while (1) {
		move_people();
		is_arrived();
		if (time <= M) go_basecamp(time);
		if (chk_all()) return time;
		time++;
	}
	return -1;
}



int main()
{
	input();
	int ans = simulation();
	printf("%d\n", ans);
	return 0;
}

 

 

베이스캠프를 찾는 BFS 를 priority queue로 구현해도 된다. 

코드는 다음과 같다. 

struct _qt
{
	int x, y;
	int move;
};

struct COMP
{
	bool operator()(const _qt &a, const _qt & b) {
		if (a.move == b.move && a.x == b.x) return a.y > b.y;
		if (a.move == b.move) return a.x > b.x;
		return a.move > b.move;	// 얘가 큐의 역할을 한다. 
	}
};
std::priority_queue<_qt, std::vector<_qt>, COMP> PQ;


void go_basecamp(int m)
{
	// init
	PQ = {};
	memset(visited, -1, sizeof(visited));

	// dir
	int dir_x[4] = { 0, 0 ,1 ,-1 };
	int dir_y[4] = { 1, -1, 0, 0 };
	
	int ex = People[m].ex;	// 편의점 기준으로 가장 가까운 베이스캠프 찾는다.
	int ey = People[m].ey;
	PQ.push({ ex, ey, 0 });
	visited[ex][ey] = 0;

	int min_dist = 0x7fffffff;
	int min_row = 0x7fffffff;
	int min_col = 0x7fffffff;

	while (!PQ.empty()) {
		_qt data = PQ.top();
		PQ.pop();

		// 우선순위를 걸어놓았기 때문에 베이스캠프를 만나면 바로 break 해줄 수 있다. 
		if (board[data.x][data.y] == 1) {	
				min_dist = data.move;
				min_row = data.x;
				min_col = data.y;
				break;
		}

		for (int p = 0; p < 4; p ++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
			if (visited[nx][ny] >= 0) continue;
			if (board[nx][ny] == 2) continue;	// 도착한 편의점, 혹은 출발한 적 있는 베이스 캠프
			PQ.push({ nx, ny, data.move + 1 });
			visited[nx][ny] = data.move + 1;
		}
	}
	board[min_row][min_col] = 2;
	People[m].x = min_row;
	People[m].y = min_col;
}