코드트리 메이즈 러너 C++

 

구현 문제이다. 

앞선 포스트에서 삼성 코테에서 좌표 회전이 많이 나온 것 같다는 글을 썼다. 이 문제 역시 좌표 회전을 포함한 문제였다.

이런 유형을 몇문제 풀어보니 대충 좌표의 규칙을 확인해서 풀면 되는 것 같다. 다행히 규칙이 여태까지 본 문제 중에서 크게 어려운 문제는 없었다.

 

이 문제의 경우, (i, j) -> (j, n-i-1) 을 만족함을 생각해서 풀어야한다.

 

이 문제의 특이한 부분은, '최단경로' 문제임에도 불구하고 dfs나 bfs로 푸는 문제가 아니라는 점이다. 

어차피 한칸만 이동이 가능하고, 이동해야하는 방향성도 명확하다. 따라서 매번 상하 -> 좌우 순으로 이동이 가능한지 확인하고 이동 가능하다면 이동을 시켜주면 된다.

 

테스트케이스 2번에서 에러가 나서 디버깅하는 시간이 조금 오래 걸렸다.

 

내가 작성한 전체 코드는 아래와 같다. 주석을 달아놔서 이해하기 쉬울 것 같다.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int ans;
int N, M, K;

int arr[11][11];
int tmp_arr[11][11];

vector<pair<int, int>> people;
vector<pair<int, int>> Exit;

void Move(void) {
	for (int i = 0;i < people.size();i++) {
		if (people[i].first == Exit[0].first && people[i].second == Exit[0].second) {
			// 이미 출구를 찾은 경우
			continue;
		}
		// 1. 상하로 이동해본다
		int nx = people[i].second, ny = people[i].first;
		if (Exit[0].first != people[i].first) {
			if (Exit[0].first < people[i].first) { // 위로 이동해야한다
				ny--;
			}
			else { // 아래로 이동해야한다
				ny++;
			}
			if (arr[ny][nx] == 0) { // 벽이 아닌 경우 이동할 수 있다
				ans++;
				people[i].first = ny;
				continue; // 종료
			}
		}

		// 2. 좌우로 이동해본다
		nx = people[i].second, ny = people[i].first;
		if (Exit[0].second != people[i].second) {
			if (Exit[0].second < people[i].second) { // 왼쪽으로 이동해야한다
				nx--;
			}
			else { // 우로 이동해야한다
				nx++;
			}
			if (arr[ny][nx] == 0) { // 벽이 아닌 경우 이동할 수 있다
				ans++;
				people[i].second = nx;
				continue;
			}
		}

		// 3. 이동할 수가 없다
		continue;
	}
}

void FindSquare(int& wx, int& wy, int& sq_t) {
	// 각 점에서 정사각형을 찾는다. 정사각형 변의 길이는 2이상이다
	for (int sq = 2; sq <= N; sq++) {
		for (int i = 0;i < N;i++) {
			for (int j = 0;j < N;j++) { // i, j는 시작점을 말한다
				if (!(i + sq <= N && j + sq <= N)) { // 범위를 넘어가면 끝낸다
					continue;
				}
				// 한명 이상의 참가자를 포함하는지 확인한다
				int contain_people = 0, contain_exit = 0;
				for (int h = 0;h < people.size();h++) {
					int x = people[h].second, y = people[h].first;
					if (y >= i && y < i + sq && x >= j && x < j + sq) {
						if (x == Exit[0].second && y == Exit[0].first) { // 이미 찾았다
							continue;
						}
						contain_people = 1;
					}
				}
				if (contain_people == 0) {
					continue;
				}
				// 출구를 포함하는지
				if (Exit[0].first >= i && Exit[0].first < i + sq && Exit[0].second >= j && Exit[0].second < j + sq) {
					contain_exit = 1;
				}
				if (contain_people && contain_exit) {
					wx = j, wy = i, sq_t = sq;
					return;
				}
			}
		}
	}
	return;
}

void Spin(int x, int y, int sq) {
	memset(tmp_arr, 0, sizeof(tmp_arr));
	// 1. 좌표를 움직임
	for (int i = y;i < y + sq;i++) {
		for (int j = x;j < x + sq;j++) {
			int ox = j - x, oy = i - y;
			int ny = ox, nx = sq - oy - 1;
			tmp_arr[ny + y][nx + x] = arr[i][j];
			if (tmp_arr[ny + y][nx + x] >= 1) {
				tmp_arr[ny + y][nx + x]--;
			}
		}
	}
	for (int i = y;i < y + sq;i++) {
		for (int j = x;j < x + sq;j++) {
			arr[i][j] = tmp_arr[i][j];
		}
	}
	// 2. 사람을 움직임
	for (int i = 0;i < people.size();i++) {
		int cx = people[i].second;
		int cy = people[i].first;
		if (cy >= y && cy < y + sq && cx >= x && cx < x + sq) {
			int ox = cx - x, oy = cy - y;
			int ny = ox, nx = sq - oy - 1;
			people[i].first = ny + y, people[i].second = nx + x;
		}
	}
	// 3. 출구를 움직임
	int cx = Exit[0].second;
	int cy = Exit[0].first;
	int ox = cx - x, oy = cy - y;
	int ny = ox, nx = sq - oy - 1;
	Exit[0].first = ny + y, Exit[0].second = nx + x;
}

bool Check(void) {
	for (int i = 0;i < people.size();i++) {
		if (!(people[i].first == Exit[0].first && people[i].second == Exit[0].second)) {
			return false;
		}
	}
	return true;
}
int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int x, y;
	cin >> N >> M >> K;
	for (int i = 0;i < N;i++) {
		for (int j = 0;j < N;j++) {
			cin >> arr[i][j];
		}
	}
	for (int i = 0;i < M;i++) {
		cin >> y >> x;
		people.push_back({ y - 1, x - 1 });
	}
	cin >> y >> x;
	Exit.push_back({ y - 1, x - 1 });
	while (K--) {
		Move();
		if (Check()) {
			break;
		}
		// 정사각형을 찾는다
		int x, y, sq;
		FindSquare(x, y, sq);
		// 회전
		Spin(x, y, sq);

	}
	cout << ans << endl << Exit[0].first + 1 << " " << Exit[0].second + 1 << endl;
	return 0;
}

테스트케이스 2번에서 에러가 나온 경우는, 정사각형을 찾는 과정에서 범위를 설정하는 부분이다. 

코드는 아래와 같다.

void FindSquare(int& wx, int& wy, int& sq_t) {
	// 각 점에서 정사각형을 찾는다. 정사각형 변의 길이는 2이상이다
	for (int sq = 2; sq <= N; sq++) {
		for (int i = 0;i < N;i++) {
			for (int j = 0;j < N;j++) { // i, j는 시작점을 말한다
				if (!(i + sq <= N && j + sq <= N)) { // 범위를 넘어가면 끝낸다
					continue;
				}

if (!(i + sq <= N && j + sq <= N)) 이 부분을 처음에 < N으로 작성했어서 2% 정도에서 계속 틀렸다.

 

잘생각해보면 등호가 들어가야한다는 것을 알 수 있다.

시험볼 때 이런 에러가 뜨면 이런 범위 부분을 잘 확인해야할 것 같다.