[삼성기출/C++] 메이즈 러너

https://www.codetree.ai/problems/maze-runner?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 꽤 참신한 아이디어가 많이 담긴 문제였다. 거두절미하고 문제를 살펴보자.

 

1. 참가자를 "어떤 자료구조"에 담아야할까?

 

 우선 여기서부터 선택지가 나뉠 것이다. 우선 지금까지 내가 했던 방법은, 커스텀 구조체를 만들어서 넣어주는 것이다. 이 문제에서는 y,x좌표 및 살아있는지 여부가 중요하므로 live 어트리뷰트를 추가해서 다음과 같이 구성할 수 있을 것이다.

typedef struct man {
	int live, y, x;
}Man;

vector<Man> v;

 

 하지만 문제가 좀 복잡한 점은, 한 칸에 "많은 사람"이 들어갈 수 있다! 뿐만 아니라 더 큰 문제는, 사람들이 "회전" 하므로, 매번 회전할때마다 y,x값을 바꿔줘야 하는데, 배열 전체가 아니라 특정 정사각형이 회전하기 때문에 이 벡터를 업데이트하는 것은 "굉장히" 어렵다.. 그러기 때문에 이번에는 벡터가 아니라, 다음과 같이 배열에 넣어줘야 한다. 배열에 넣어야 회전 로직을 구현하기 쉽다.

int land[14][14];
int land_temp[14][14];
int man_land[14][14];
int man_temp[14][14];
pii out;

 

 다음과 같이 "벽"을 나타낸 land 배열과, 사람을 나타내는 man_land 배열 두 개로 나누고, 회전 로직때마다 동시에 두 배열 모두 회전시켜주면 된다. 그리고 정사각형을 찾는 로직에서 out의 y,x 좌표가 항상 필요하므로, 이것을 따로 저장해 두자.

 

 2. 정사각형을 정하는 로직을 어떻게 구해야할까?

 

 이 부분에서 상당히 애를 먹었다. 우선 이렇게 복잡한 요구사항이 있을 경우는 우선 한 조건을 "고정"하는 방법이 편하다. 어떤 조건을 고정할까? 바로 좌상단 좌표이다. 좌상단 좌표를 고정하고, 너비(=높이)만 조정해준다면 최소 크기의 정사각형을 쉽게 구할 수 있다. 로직은 다음과 같다.

	// 2. make_square
	h = 1e9;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i <= out.first && j <= out.second) {
				make_square(i, j);
			}
		}
	}

 

 위 로직은 좌상단 좌표가 out보다 좌상단에 있는지를 파악하는 부분이고, make_square() 함수에서는 out을 포함하는 square에서 man을 탐지하면 리턴하는 함수이다. 다음과 같다.

void make_square(int _r, int _c) {
	int _h = max(out.first - _r, out.second - _c);
	for (int i = _h; max(_r, _c) + i <= n; i++) {
		if (h <= i) return; // h가 작은게 우선 나머지는 자동정렬
		for (int y = _r; y <= _r + i; y++) {
			for (int x = _c; x <= _c + i; x++) {
				if (man_land[y][x]) {
					r = _r; c = _c; h = i; return;
				}
			}
		}
	}
	return;
}

 

 말이 쉽게지 이 정사각형 구하는 함수가 1번문제치고 정말 어려웠다. 하지만 한번 배웠으므로 실전에서는 좌상단을 고정한다는 아이디어를 명심하면 쉽게 풀 수 있을 것이다. 최종 코드는 다음과 같다.

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
void init() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); }

int land[14][14];
int land_temp[14][14];
pii out;
int n, m, k;
int man_land[14][14];
int man_temp[14][14];
int ret;
int cnt;
int r, c, h;
const int dy[] = { -1, 1, 0, 0 }; // 상 하 우 좌
const int dx[] = { 0, 0, 1, -1 };

bool is_out(int y, int x) {
	if (y<1 || y > n || x < 1 || x > n) return true;
	return false;
}

int calc(int y, int x) {
	return abs(out.first - y) + abs(out.second - x);
}

void print() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << land[i][j] << ',' << man_land[i][j] << ' ';
		}
		cout << '\n';
	}
	cout << '\n';
}

void man_move(int y, int x) {
	int dist = calc(y, x);
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i], nx = x + dx[i];
		if (is_out(ny, nx) || land[ny][nx]) continue;
		if (ny == out.first && nx == out.second) { // 탈출
			cnt+=man_land[y][x]; ret += man_land[y][x]; return;
		}
		if (dist > calc(ny,nx)) {
			ret += man_land[y][x]; 
			man_temp[ny][nx] += man_land[y][x]; return;
		}
	}
	// 움직일수없을때
	man_temp[y][x] += man_land[y][x];
	return;
}

void make_square(int _r, int _c) {
	int _h = max(out.first - _r, out.second - _c);
	for (int i = _h; max(_r, _c) + i <= n; i++) {
		if (h <= i) return; // h가 작은게 우선 나머지는 자동정렬
		for (int y = _r; y <= _r + i; y++) {
			for (int x = _c; x <= _c + i; x++) {
				if (man_land[y][x]) {
					r = _r; c = _c; h = i; return;
				}
			}
		}
	}
	return;
}

void cw90() {
	int out_changed = false;
	for (int i = 0; i <= h; i++) {
		for (int j = 0; j <= h; j++) {
			if (out_changed == 0 && r + i == out.first && c + j == out.second) {
				out.first = r + j;
				out.second = c + h - i;
				out_changed = true;
				//cout << out.first << " : " << out.second << '\n';
			}
			land_temp[r + j][c + h - i] = land[r + i][c + j];
			man_temp[r + j][c + h - i] = man_land[r + i][c + j];
			if (land_temp[r + j][c + h - i]) land_temp[r + j][c + h - i]--;
		}
	}
	for (int i = 0; i <= h; i++) {
		for (int j = 0; j <= h; j++) {
			land[r + i][c + j] = land_temp[r + i][c + j];
			man_land[r + i][c + j] = man_temp[r + i][c + j];
		}
	}
}

void go() {
	// 1. man_move
	memset(man_temp, 0, sizeof(land));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (man_land[i][j]) man_move(i, j);
		}
	}
	memcpy(man_land, man_temp, sizeof(man_temp));
	if (cnt == m) return;
	// 2. make_square
	h = 1e9;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i <= out.first && j <= out.second) {
				make_square(i, j);
			}
		}
	}
	//cout << r << " : " << c << " : " << h << '\n';
	// 3. rotate
	cw90();
	//print();
	return;
}

int main() {
	init();
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> land[i][j];
		}
	}
	for (int i = 0; i < m; i++) {
		int y, x; cin >> y >> x;
		man_land[y][x]++;
	}
	cin >> out.first >> out.second;
	for (int i = 0; i < k; i++) {
		//cout << i << " turn " << '\n';
		go();
		if (cnt == m) break;
	}
	cout << ret << '\n' << out.first << ' ' << out.second << '\n';
	return 0;
}

 

 cnt 조작 실수로 첫 시도에서 런타임 에러가 나왔다. 이러한 실수는 꼭 조심해야할 것이다.