[C++] 백준 17837 새로운 게임 2

문제 링크

---

https://www.acmicpc.net/problem/17837

17837번: 새로운 게임 2

 

접근 방법

---

typedef struct horse {
	int y;
	int x;
	int d;
};
horse h[MAXK];
int N, K, map[MAX][MAX];
vector<int> section[MAX][MAX];
const pair<int, int> direction[5] = { {0, 0}, {0, 1}, {0, -1}, {-1, 0}, {1, 0} };

위와 같은 구조의 변수를 정의하여 사용하였다.

section[][]에는 말이 stack된 것을 vector로 표현하였다.

 

이 문제를 풀면서 가장 오래걸렸던 부분은 다음 영역으로 이동할 때, 다음 영역에 존재하는 다른 말보다 위에 쌓아야 하는 조건을 반대로 해석해서 시간을 잡아먹은 것과, 말이 벽이나 파란색 영역을 만났을 때, 뒤집어서 다시 전진하는 부분이었다.

 

이 문제는 특별한 알고리즘이 있는 문제가 아니라서 설명은 생략하겠다. 코드를 참고 바란다.

 

 

소스 코드

---

#include <vector>
#include <iostream>
#include <algorithm>
#define MAX 13
#define MAXK 11
using namespace std;
typedef struct horse {
	int y;
	int x;
	int d;
};
horse h[MAXK];
int N, K, map[MAX][MAX];
vector<int> section[MAX][MAX];
const pair<int, int> direction[5] = { {0, 0}, {0, 1}, {0, -1}, {-1, 0}, {1, 0} };

void update_coord(vector<int>& upper, int ny, int nx) {
	for (int i = 0; i < upper.size(); ++i) {
		h[upper[i]].y = ny;
		h[upper[i]].x = nx;
	}
}

// k번째 말을 움직인다.
bool move(int ny, int nx, int k) {
	vector<int>& from = section[h[k].y][h[k].x];
	vector<int>& to = section[ny][nx];
	vector<int> upper;
	for (int i = 0; i < from.size(); ++i) {
		if (from[i] == k) {
			upper.assign(from.begin() + i, from.end());
			from.assign(from.begin(), from.begin() + i);
		}
	}
	update_coord(upper, ny, nx);
	if (map[ny][nx] == 0) { // 흰색
		if (to.empty()) // 다음칸이 비어있다면
			to = upper; // 그냥 이동
		else { // 다음 칸에 말이 이미 있는 경우
			for (int i = 0; i < upper.size(); ++i) {
				to.push_back(upper[i]);
			}
		}
	}
	else if (map[ny][nx] == 1) { // 빨간색
		reverse(upper.begin(), upper.end()); // 일단 뒤집는다.
		if (to.empty()) // 다음칸이 비어있다면
			to = upper; // 그냥 이동
		else { // 다음 칸에 말이 이미 있는 경우
			for (int i = 0; i < upper.size(); ++i) {
				to.push_back(upper[i]);
			}
		}
	}

	if (to.size() >= 4) return true;
	else return false;
}

bool is_movable(int ny, int nx) {
	if (ny > N || nx > N || ny < 1 || nx < 1 || map[ny][nx] == 2) return false;
	return true;
}

void update_direct(int k) {
	int opposite_d = 0;
	if (h[k].d == 1) opposite_d = 2;
	else if (h[k].d == 2) opposite_d = 1;
	else if (h[k].d == 3) opposite_d = 4;
	else if (h[k].d == 4) opposite_d = 3;
	h[k].d = opposite_d;
}

bool turn_back(int y, int x, int k) {
	int i;
	vector<int>& from = section[y][x];
	vector<int> upper;
	for (i = 0; i < from.size(); ++i) {
		if (k == from[i]) {
			upper.assign(from.begin() + i, from.end());
		}
	}
	update_direct(k);
	int ny = y + direction[h[k].d].first;
	int nx = x + direction[h[k].d].second;
	if (!is_movable(ny, nx)) return false;
	return move(ny, nx, k);
}

bool turn() {
	for (int k = 1; k <= K; ++k) {
		int ny = h[k].y + direction[h[k].d].first;
		int nx = h[k].x + direction[h[k].d].second;
		if (!is_movable(ny, nx)) {
			if (turn_back(h[k].y, h[k].x, k)) return true;
		}
		else {
			if (move(ny, nx, k)) return true;
		}
	}
	return false;
}

int solve() {
	int ret = 0;
	while (ret < 1000) {
		++ret;
		if (turn()) break;
	}
	if (ret >= 1000) return -1;
	else return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N >> K;
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j)
			cin >> map[i][j];
	for (int i = 1; i <= K; ++i) {
		cin >> h[i].y >> h[i].x >> h[i].d;
		section[h[i].y][h[i].x].push_back(i);
	}
	cout << solve();
	return 0;
}

개발 환경 : VS2019

질문, 지적 환영합니다!