백준 17837번 새로운 게임2

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

17837번: 새로운 게임 2

 

새로운 게임2 입니다!

삼성코테기출이라고 하네요

 

 

 

 

새로운 게임2보다 조금 더 쉬운 문제가 있습니다.

혹시 2먼저 도전하셨다가 못풀겠으면 이거 먼저 푸는게 좋을 듯 합니다.

 

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

17780번: 새로운 게임

 

 

 

 

 

<접근방법>

새로운 게임과 접근방법이 비슷합니다. 하지만 새로운 게임2는 내 위에 있는 말이 뭐가 있는지 항상 알 필요가 있습니다.

그래서 저는 (2차원배열 벡터)+ (말의 구조체에 내 위에 있는 말이 들어가는 벡터) 이렇게 하려고 했습니다.

하지만 제 구현력으로는 어려웠고 다른 방법을 모색하다가 2차원배열 벡터가 있고 한 칸에 몇 번째로 있는지만 알면

기능구현이 가능하지 않을까 생각했습니다.

 

 

 

---

 

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct state {
	int y, x, d, num;
};

int n, k;
int color[12][12]; //0 흰색 1 빨간색 2 파란색
vector<int> w[12][12];
state horse[10];
int dy[4] = {0, 0, -1, 1};
int dx[4] = {1, -1, 0, 0};

bool check_end() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (w[i][j].size() >= 4) {
				return true;
			}
		}
	}
	return false;
}

void change_dir(int h, int d) {
	switch (d) {
	case 0: horse[h].d = 1; break;
	case 1: horse[h].d = 0; break;
	case 2: horse[h].d = 3; break;
	case 3: horse[h].d = 2; break;
	default: break;}
}

void move(int h, int y, int x, int ty, int tx, int d, int col) {
	int num = horse[h].num;
	int af_sz = w[ty][tx].size();
	int num_maker = 0;

	switch (col) {
	case 0:
		//옮기기 작업
		//w에 옮기는 작업 해주고
		//목표지점의 말들에 대해서 num증가
		//옮겨지는 말들의 num증가
		for (int i = num; i < w[y][x].size(); i++) {
			int tmp = w[y][x][i];

			horse[tmp].num = num_maker++; // 옮겨지는 말에 대하여 순서대로 0, 1, 2... 더해주기
			horse[tmp].num += af_sz; // 목표지점의 사이즈만큼 더해주기
			horse[tmp].y = ty;
			horse[tmp].x = tx;

			w[ty][tx].push_back(tmp);
		}
		w[y][x].erase(w[y][x].begin() + num, w[y][x].end());
		break;

	case 1:
		for (int i = w[y][x].size() - 1; i >= num; i--) {
			int tmp = w[y][x][i];

			horse[tmp].num = num_maker++;
			horse[tmp].num += af_sz;
			horse[tmp].y = ty;
			horse[tmp].x = tx;

			w[ty][tx].push_back(tmp);
			w[y][x].pop_back();
		}
		break;

	case 2:
		change_dir(h, d);
		d = horse[h].d;
		ty = y + dy[d];
		tx = x + dx[d];

		//기저사례
		//방향 바꿨는데 또 파랑색
		if (color[ty][tx] == 2) return;
		//범위 밖
		if (ty < 0 || ty >= n || tx < 0 || tx >= n) return;

		move(h, y, x, ty, tx, d, color[ty][tx]);
		break;

	default:
		break;
	}
}

int simul() {
	int res = 0;
	while (++res < 1000) {
		for (int i = 0; i < k; i++) {
			int y = horse[i].y;
			int x = horse[i].x;
			int d = horse[i].d;
			int ty = y + dy[d];
			int tx = x + dx[d];

			if (ty < 0 || ty >= n || tx < 0 || tx >= n) {// 범위 밖
				move(i, y, x, ty, tx, d, 2);
			}
			else {
				move(i, y, x, ty, tx, d, color[ty][tx]);
			}
			
			if (check_end()) return res;
		}
	}
	return -1;
}


int main() {
	cin >> n >> k;

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

	for (int i = 0; i < k; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--; c--;
		horse[i].y = a; horse[i].x = b; horse[i].d = c; horse[i].num = 0;
		w[a][b].push_back(i);
	}

	cout << simul() << '\n';

	return 0;
}

 

 

 

---

 

 

 

<느낀 점>

모듈은 여러 상황이 사용할 수 있게끔 해야한다.