마법의 숲 탐색

Simulation, BFS

평균 : 180'

---

sol : 150' 42''

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

Learnings

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

#define MAX_K 1001
#define MAX_R 74
#define MAX_C 72

#define WALL -1
#define EMPTY 0
#define DIRECTION 4

using namespace std;

// 북, 동, 남, 서
int ds[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
int r, c, k;

// 자료 구조
pair<int, int> elemental[MAX_K];
// 0~2 : 예비 공간, 3~(r+3) : 숲
// 골렘 id로 표시
int grid[MAX_R][MAX_C];
int answer;
bool visited[MAX_R][MAX_C];
// 각 id 골렘별 출구 정보
vector<pair<int, int>> paths;

//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////

void Debug() {
	cout << endl << "DEBUG" << endl;
	for (int i = 0; i <= r + 2; i++) {
		for (int j = 0; j <= c + 1; j++) {
			if (grid[i][j] == WALL) cout << 'W' << ' ';
			else cout << grid[i][j] << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG FIN" << endl;
}

void Init() {
	cin >> r >> c >> k;

	for (int i = 1; i <= k; i++) {
		int c, d;
		cin >> c >> d;
		elemental[i] = { c, d };
	}

	for (int i = 0; i <= r + 3; i++) {
		// 동쪽 벽
		grid[i][0] = WALL;
		// 서쪽 벽
		grid[i][c + 1] = WALL;
	}

	for (int j = 0; j <= c + 1; j++) {
		// 남쪽 벽
		grid[r + 3][j] = WALL;
	}
}

void ClearGrid() {
	for (int i = 0; i <= r + 2; i++) {
		for (int j = 1; j <= c; j++) {
			grid[i][j] = EMPTY;
		}
	}
}

bool InGrid(int i, int j) {
	return 3 <= i && i <= r + 2 && 1 <= j && j <= c;
}

void InitVisited() {
	for (int i = 3; i <= r + 2; i++) {
		for (int j = 1; j <= c; j++) {
			visited[i][j] = false;
		}
	}
}

bool CheckClear(int g[3]) {
	if (g[0] <= 3) return true;
	// just in case
	if (g[1] <= 1 || g[1] >= c) return true;
	return false;
}

bool Down(int g[3]) {
	if (grid[g[0] + 1][g[1] - 1] == EMPTY && grid[g[0] + 1][g[1] + 1] == EMPTY && grid[g[0] + 2][g[1]] == EMPTY) {
		g[0]++;
		return true;
	}
	return false;
}

bool WestRotateAndDown(int g[3]) {
	// West Rotate : 동 -> 북 -> 서 -> 남 (1 -> 0 -> 3 -> 2 -> ... )
	if (grid[g[0] - 1][g[1] - 1] == EMPTY && grid[g[0]][g[1] - 2] == EMPTY && grid[g[0] + 1][g[1] - 1] == EMPTY && grid[g[0] + 1][g[1] - 2] == EMPTY && grid[g[0] + 2][g[1] - 1] == EMPTY) {
		g[0]++, g[1]--;
		g[2] = (g[2] + 3) % 4;
		return true;
	}
	return false;
}

bool EastRotateAndDown(int g[3]) {
	// East Rotate : 북 -> 동 -> 남 -> 서 (0 -> 1 -> 2 -> 3 -> ... )
	if (grid[g[0] - 1][g[1] + 1] == EMPTY && grid[g[0]][g[1] + 2] == EMPTY && grid[g[0] + 1][g[1] + 1] == EMPTY && grid[g[0] + 1][g[1] + 2] == EMPTY && grid[g[0] + 2][g[1] + 1] == EMPTY) {
		g[0]++, g[1]++;
		g[2] = (g[2] + 1) % 4;
		return true;
	}
	return false;
}

void Drop(int g[3]) {
	while (true) {
		// 1. 남쪽 이동 가능 여부
		if (Down(g)) continue;
		// 2. 서쪽 회전 후 down
		if (WestRotateAndDown(g)) continue;
		// 3. 동쪽 회전 후 down
		if (EastRotateAndDown(g)) continue;

		break;
	}
}

void Draw(int id, int g[3]) {
	for (int d = 0; d < DIRECTION; d++) {
		grid[g[0] + ds[d][0]][g[1] + ds[d][1]] = id;
	}
	grid[g[0]][g[1]] = id;
}

void ElementalDown(int id, int g[3]) {
	int si = g[0], sj = g[1], cur_id = id;
	int path_i = si + ds[g[2]][0], path_j = sj + ds[g[2]][1];
	paths.resize(k + 1);
	paths[id] = { path_i, path_j };

	queue<tuple<int, int, int>> q;
	int max_r = si;
	InitVisited();

	q.push({ si, sj, cur_id });
	while (!q.empty()) {
		int ci, cj, cid;
		tie(ci, cj, cid) = q.front();
		path_i = paths[cid].first, path_j = paths[cid].second;

		q.pop();

		visited[ci][cj] = true;

		for (int d = 0; d < DIRECTION; d++) {
			int ni = ci + ds[d][0], nj = cj + ds[d][1], nid = cid;
			

			if (InGrid(ni, nj) && !visited[ni][nj]) {
				// 방문하지 않은 현재 id칸에서만 이동 가능
				if (grid[ni][nj] == cid) {
					// 더 남쪽인 칸일 경우 업데이트
					if (ni > max_r)	max_r = ni;
					q.push({ ni, nj, nid});
				}
				// 만약 현재칸이 출구이고, 다음 칸이 다른 골렘인 경우
				else if ((ci == path_i && cj == path_j) && grid[ni][nj] > 0) {
					// 더 남쪽인 칸일 경우 업데이트
					if (ni > max_r) max_r = ni;
					// 다음 칸 골렘으로 id 업데이트
					nid = grid[ni][nj];
					q.push({ ni, nj, nid });
				}
			}
		}
	}
	max_r -= 2;
	answer += max_r;
}

void FinalPlace(int id, int g[3]) {
	// 1. Draw Grid
	Draw(id, g);

	// 2. Find Lowest Place
	ElementalDown(id, g);
}

int main() {
	Init();

	for (int e = 1; e <= k; e++) {
		// Set Gollem at c
		int curGollem[3] = { 1, elemental[e].first, elemental[e].second };

		// Drop the Gollem
		Drop(curGollem);

		// Check Outbound
		if (CheckClear(curGollem)) {
			ClearGrid();
		}
		else {
			// Get Final place of elemental
			FinalPlace(e, curGollem);
		}
	}

	cout << answer;

	return 0;
}