코드트리 빵

Simulation, BFS

• 평균 : 180'

---

sol : 117' 13''

• 수행 시간 : 8ms
• 메모리 : 0MB

New Skills

• 요즘 설계를 시작할 때 새롭게 만든 습관이 있다. 주어진 조건들에 대해 세부 구현 사항을 고민하려는 관성을 어떻게든 참고, 큰 그림에서 어떤 기능들이 있는지 주어진 순서에 따라 먼저 배치하는 것. 이렇게 하니 기능별 함수 분리, 디버깅 명확성, 가독성 등 모든 면에서 훨씬 좋아졌다.

Learnings

• 모범 답안을 보니 BFS를 한 번 돌려서 원하는 기능들을 수행한다. 내 코드에서는 두 번의 BFS를 구현하는데, 이는 더 추상화할 여지가 있음을 의미한다.
• 작년에는 파이썬으로 이 문제를 풀었던 기록이 있다. 확실히 작년에 비해 훨씬 코드가 간결해지고, 명확해졌다. 성장하고 있구나!

#include <iostream>
#include <vector>
#include <utility>
#include <tuple>
#include <queue>
#include <climits>

#define MAX_N 16
#define EMPTY 0
#define BASE_CAMP 1
#define BANNED -1

using namespace std;

int n, m;
int grid[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
bool finished = false;
int minute;
int ds[4][2] = { {-1, 0}, {0, -1}, {0, 1}, {1, 0} };

// i, j | index : store id
vector<pair<int, int>> store;

struct person {
	int id;
	int i;
	int j;
	bool isInGrid;
	bool isArrived;

	person() {};
	person(int _id, int _i, int _j, bool _isInGrid, bool _isArrived) :
		id(_id), i(_i), j(_j), isInGrid(_isInGrid), isArrived(_isArrived) {
	}
};

vector<person> people;

bool InGrid(int i, int j) {
	return 1 <= i && i <= n && 1 <= j && j <= n;
}

void Debug() {
	cout << endl << "DEBUG" << endl;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << grid[i][j];
		}
		cout << endl;
	}
	cout << "DEBUG FIN" << endl;
}

void InitVisited() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			visited[i][j] = false;
		}
	}
}

void Init() {
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> grid[i][j];
		}
	}

	store.resize(m + 1);
	people.resize(m + 1);
	for (int i = 1; i <= m; i++) {
		cin >> store[i].first >> store[i].second;
		people[i] = person(i, 0, 0, false, false);
	}
}

pair<int, int> GetSP(person p) {
	// p번째 사람의 Shortest path를 찾아 당장 이동할 다음 칸 하나를 리턴.
	// store에서 출발하여 p에 도달한 경우, 도달하기 직전 칸을 리턴하면 끝.
	int start_i, start_j, goal_i, goal_j;
	// 목표 : p
	goal_i = p.i, goal_j = p.j;
	// 시작점 : store
	tie(start_i, start_j) = store[p.id];

	InitVisited();
	queue<pair<int, int>> q;
	q.push({ start_i, start_j });
	visited[start_i][start_j] = true;

	while (!q.empty()) {
		int ci = q.front().first;
		int cj = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ni = ci + ds[d][0], nj = cj + ds[d][1];
			if (InGrid(ni, nj) && !visited[ni][nj]) {
				if (ni == goal_i && nj == goal_j) {
					// 다음 칸이 목적지일 경우, 현재 칸 리턴(이번 턴에 이동할 칸)
					return { ci, cj };
				}
				else if (grid[ni][nj] != BANNED) {
					q.push({ ni, nj });
					visited[ni][nj] = true;
				}
			}
		}
	}
}

void Move() {
	for (int p = 1; p <= m; p++) {
		if (people[p].isInGrid && !people[p].isArrived) {
			int ni, nj;
			tie(ni, nj) = GetSP(people[p]);

			people[p].i = ni, people[p].j = nj;
		}
	}
}

void ArrivalCheck() {
	for (int p = 1; p <= m; p++) {
		if (people[p].isArrived || !people[p].isInGrid) continue;

		if (people[p].i == store[p].first && people[p].j == store[p].second) {
			people[p].isArrived = true;
			grid[people[p].i][people[p].j] = BANNED;
		}
	}
}

void FinishCheck() {
	for (int p = 1; p <= m; p++) {
		if (!people[p].isArrived) return;
	}

	finished = true;
}

pair<int, int> ChooseBC(person p) {
	int start_i = store[p.id].first, start_j = store[p.id].second;
	InitVisited();

	queue<tuple<int, int, int>> q;
	q.push({ start_i, start_j, 0 });
	visited[start_i][start_j] = true;
	pair<int, int> basecamp = { -1, -1 };
	int minDistance = INT_MAX;

	while (!q.empty()) {
		int ci, cj, cd;
		tie(ci, cj, cd) = q.front();
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ni = ci + ds[d][0], nj = cj + ds[d][1], nd = cd + 1;

			if (InGrid(ni, nj) && !visited[ni][nj] && grid[ni][nj] != BANNED) {
				if (grid[ni][nj] == BASE_CAMP) {
					// 1. 처음 발견한 경우
					if (basecamp.first == -1 && basecamp.second == -1) {
						basecamp = { ni, nj };
						minDistance = nd;
					}
					// 2. 최솟값을 발견한 경우
					else if (minDistance > nd) {
						basecamp = { ni, nj };
						minDistance = nd;
					}
					// 3. 거리가 같을 경우
					else if (minDistance == nd) {
						// 행이 더 작다면
						if (basecamp.first > ni) {
							basecamp = { ni, nj };
						}
						// 행이 같을 경우
						else if (basecamp.first == ni) {
							// 열이 더 작다면
							if (basecamp.second > nj) {
								basecamp = { ni, nj };
							}
						}
					}
				}
				else {
					q.push({ ni, nj, nd });
					visited[ni][nj] = true;
				}
			}
		}
	}

	return basecamp;
}

void GetIn() {
	if (minute > m) return;

	int t = minute;
	int base_i, base_j;
	tie(base_i, base_j) = ChooseBC(people[t]);

	people[t].i = base_i, people[t].j = base_j;
	people[t].isInGrid = true;
	grid[base_i][base_j] = BANNED;
}

int main() {
	Init();

	while (!finished) {
		minute++;
		// 1. people move 1 cell in shortest path
		Move();

		// 2. if arrived, the cell is banned
		ArrivalCheck();

		// 3. t's person get in if t <= m, banning the cell.
		GetIn();

		// If everyone arrived, game fin
		FinishCheck();
	}

	cout << minute;

	return 0;
}