<Baekjoon> #17780 #17837 새로운 게임1,2 c++

12446 단어 beakjoonalgorithm"삼성SW""삼성SW"

새로운 게임2를 풀면 새로운 게임1은 바로 풀 수 있으니 2 풀이만 한다
#17837 새로운 게임2

💡Idea

  • map상에는 각 색깔이 저장되어 있고, 각 칸에는 여러 개의 체스가 저장되기 때문에 map에 색을 저장하는 벡터와, 각map에 여러 개의 체스를 저장할 벡터를 만들어야 한다
  • 각각의 체스는 위치 (y,x)와 방향을 가지기 때문에 이 셋을 저장할 구조체를 따로 선언한다
  • 각 체스를 움직일 때, 현재 체스보다 위에 있는 체스들을 함께 움직이기 때문에 현재 움직이려는 체스가 현재 칸에서 몇 번째에 위치해있는지 찾는 함수가 필요하다
  • 한 칸에 4개 이상의 체스가 존재하면 중지해야 하기 때문에 매번 체스를 움직일 때마다 각 칸에 있는 체스의 개수를 세는 함수가 필요하다

✏️1. Initialize

  • 색을 저장하는 벡터(map)와 여러 개의 체스를 저장할 벡터(mapState)를 만든다
vector<vector<int>> map;
vector<int> mapState[MAX][MAX];
  • Chess를 만들고 입력으로 체스의 위치, 방향이 들어오면 각 체스에 저장해준다
  • mapState에서 각 위치에 체스 번호를 넣어준다
struct CHESS {
	int y, x;
	int dir;
};
vector<CHESS> chess;
chess = vector<CHESS>(K);

for (int i = 0; i < K; i++) {
  int y, x, d;
  cin >> y >> x >> d;
  chess[i].y = y;
  chess[i].x = x;
  chess[i].dir = d;
  mapState[y][x].push_back(i);
}

✏️2. Game Start

Solution

  • 게임은 게임 횟수가 1000보다 크거나, 한 칸에 4개 이상의 말이 있는 경우 종료된다
  • 매번 0번~K-1번의 체스가 움직이는데, moveChess()에서 체스가 움직이는 연산을 수행한다
  • moveChess에는 현재 위치 (y,x), 움직일 위치 (ny, nx), 현재 체스가 현재 칸 위에서 몇 번째에 있는지 나타내는 'pos', 다음 위치의 색깔 (map[ny][nx]), 현재 체스의 번호 i 가 인자로 넘어간다
  • 매번 움직일 때마다 한 칸에 4개 이상의 체스가 있는지 확인하는 checkVaild()함수를 호출해서 확인한다
int solution() {
	int cnt = 0;
	bool vaild = true;
	while (1) {
		if (cnt > 1000) return -1;

		for (int i = 0; i < K; i++) {
			int y = chess[i].y;
			int x = chess[i].x;
			int dir = chess[i].dir;

			int ny = y + dy[dir];
			int nx = x + dx[dir];

			int pos = findPosition(y, x, i);

			if (ny > 0 && nx > 0 && ny <= N && nx <= N)
				moveChess(y, x, ny, nx, pos, map[ny][nx], i);
			else moveChess(y, x, ny, nx, pos, BLUE, i);

			vaild = checkValid();
			if (!vaild) break;
		}
		cnt++;
		if (!vaild) break;
	}
	return cnt;
}

moveChess(int y, int x, int ny, int nx, int pos, int colour, int idx)

  • white: 다음 칸이 white이면 현재 체스 위치 pos에서부터 끝까지 차례대로 다음 위치로 옮겨주고 옮긴 갯수만큼 원래 있던 칸에서 제거해준다
	if (colour == WHITE) {
		int movingChess = 0;
		for (int i = pos; i < mapState[y][x].size(); i++) {
			int n = mapState[y][x][i];
			mapState[ny][nx].push_back(n);
			chess[n].y = ny;
			chess[n].x = nx;
			movingChess++;
		}
		for (int i = 0; i < movingChess; i++)
			mapState[y][x].pop_back();
	}
  • Red: 다음 칸이 red이면 끝에서부터 현재 위치 pos까지 차례대로 다음 위치로 옮겨주고 옮긴 갯수만큼 원래 있던 칸에서 제거해준다
	else if (colour == RED) {
		int movingChess = 0;
		for (int i = mapState[y][x].size()-1; i>=pos; i--) {
			int n = mapState[y][x][i];
			mapState[ny][nx].push_back(n);
			chess[n].y = ny;
			chess[n].x = nx;
			movingChess++;
		}
		for (int i = 0; i < movingChess; i++)
			mapState[y][x].pop_back();
	}
  • Blue: 다음 칸이 blue인 경우 먼저 체스의 방향을 반대로 바꾸어 다시 다음 위치를 탐색한다. 만약 다음 카이 범위를 벗어나거나 다시 blue인 경우는 탐색을 하지 않고 그렇지 않은 경우에는 위에서 white나 red로 이동하는 방법으로 이동을 한다
	else if (colour == BLUE) {
		int d = chess[idx].dir;
		d = changeDir(d);
		chess[idx].dir = d;
		int nny = y + dy[d];
		int nnx = x + dx[d];

		if (nny <= 0 || nnx <= 0 || nny > N || nnx > N) return;
		if (map[nny][nnx] == BLUE) return;
		
		moveChess(y, x, nny, nnx, pos, map[nny][nnx], idx);
	}

🔖Source Code

#include <iostream>
#include <vector>

using namespace std;

const int WHITE = 0;
const int RED = 1;
const int BLUE = 2;
const int MAX = 13;

struct CHESS {
	int y, x;
	int dir;
};
vector<CHESS> chess;

int dy[] = { 0,0,0,-1,1 };
int dx[] = { 0,1,-1,0,0 };

int N, K;

vector<vector<int>> map;
vector<int> mapState[MAX][MAX];

int changeDir(int dir) {
	switch (dir) {
	case 1: return 2;
	case 2: return 1;
	case 3: return 4;
	case 4: return 3;
	}
}
void input() {
	cin >> N >> K;
	map = vector<vector<int>>(N + 1, vector<int>(N + 1));
	chess = vector<CHESS>(K);

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> map[i][j];

	for (int i = 0; i < K; i++) {
		int y, x, d;
		cin >> y >> x >> d;
		chess[i].y = y;
		chess[i].x = x;
		chess[i].dir = d;

		mapState[y][x].push_back(i);
	}
}
bool checkValid() {
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			if (mapState[i][j].size() >= 4) return false;
	return true;
}
int findPosition(int y, int x, int idx) {
	for (int i = 0; i < mapState[y][x].size(); i++)
		if (mapState[y][x][i] == idx) return i;
}
void moveChess(int y, int x, int ny, int nx, int pos, int colour, int idx) {

	if (colour == WHITE) {
		int movingChess = 0;
		for (int i = pos; i < mapState[y][x].size(); i++) {
			int n = mapState[y][x][i];
			mapState[ny][nx].push_back(n);
			chess[n].y = ny;
			chess[n].x = nx;
			movingChess++;
		}
		for (int i = 0; i < movingChess; i++)
			mapState[y][x].pop_back();
	}

	else if (colour == RED) {
		int movingChess = 0;
		for (int i = mapState[y][x].size()-1; i>=pos; i--) {
			int n = mapState[y][x][i];
			mapState[ny][nx].push_back(n);
			chess[n].y = ny;
			chess[n].x = nx;
			movingChess++;
		}
		for (int i = 0; i < movingChess; i++)
			mapState[y][x].pop_back();
	}

	else if (colour == BLUE) {
		int d = chess[idx].dir;
		d = changeDir(d);
		chess[idx].dir = d;
		int nny = y + dy[d];
		int nnx = x + dx[d];

		if (nny <= 0 || nnx <= 0 || nny > N || nnx > N) return;
		if (map[nny][nnx] == BLUE) return;

		moveChess(y, x, nny, nnx, pos, map[nny][nnx], idx);
	}
}
int solution() {
	int cnt = 0;
	bool vaild = true;
	while (1) {
		if (cnt > 1000) return -1;

		for (int i = 0; i < K; i++) {
			int y = chess[i].y;
			int x = chess[i].x;
			int dir = chess[i].dir;

			int ny = y + dy[dir];
			int nx = x + dx[dir];

			int pos = findPosition(y, x, i);

			if (ny > 0 && nx > 0 && ny <= N && nx <= N)
				moveChess(y, x, ny, nx, pos, map[ny][nx], i);
			else moveChess(y, x, ny, nx, pos, BLUE, i);

			vaild = checkValid();
			if (!vaild) break;
		}

		cnt++;
		if (!vaild) break;
	}
	return cnt;
}

int main() {
	input();
	cout<<solution()<<endl;

	return 0;
}

🔖Source Code2 (새로운 게임1)

  • 이 경우에는 현재 움직이려는 체스 i가 현재 위치에서 가장 아래에 있는 체스인지 즉, mapState[y][x][0]==i 인지 확인하고 그렇다면 움직이는 연산을 수행하면 된다
#include <iostream>
#include <vector>

using namespace std;

const int MAX = 13;
const int WHITE = 0;
const int RED = 1;
const int BLUE = 2;

int dy[] = {0,0,0,-1,1};
int dx[] = {0,1,-1,0,0};

int N, K;

vector<vector<int>> map;
vector<int> mapState[MAX][MAX]; //각 map의 칸에 몇 개의 체스가 저장되어 있는지

struct Chess {
	int y, x;
	int dir;
};
Chess chess[11];

int changeDir(int dir) {
	switch (dir) {
	case 1: return 2;
	case 2: return 1;
	case 3: return 4;
	case 4: return 3;
	}
}

void moveChess(int y, int x, int ny, int nx, int colour, int idx) {
	if (colour == WHITE) {
		for (int i = 0; i < mapState[y][x].size(); i++) {
			int n = mapState[y][x][i];
			mapState[ny][nx].push_back(n);
			chess[n].y = ny;
			chess[n].x = nx;
		}
		mapState[y][x].clear();
	}
	else if (colour == RED) {
		for (int i = mapState[y][x].size()-1; i>=0; i--) {
			int n = mapState[y][x][i];
			mapState[ny][nx].push_back(n);
			chess[n].y = ny;
			chess[n].x = nx;
		}
		mapState[y][x].clear();
	}
	else if (colour == BLUE) {
		int d = chess[idx].dir;
		d = changeDir(d);
		chess[idx].dir = d;

		int nny = y + dy[d];
		int nnx = x + dx[d];

		if (nny > 0 && nnx > 0 && nny <= N && nnx <= N) 
			if (map[nny][nnx]!=BLUE)
				moveChess(y, x, nny, nnx, map[nny][nnx], idx);
	}
}
bool vaildState() {
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			if (mapState[i][j].size() >= 4) return false;
	return true;
}
int solution() {
	bool vaild = true;
	int cnt = 0;
	while (1) {

		if (cnt > 1000) return -1;

		for (int i = 0; i < K; i++) {
			int y = chess[i].y;
			int x = chess[i].x;
			int d = chess[i].dir;

			//check - is in the bottom
			//int z = mapState[y][x].size() - 1;
			if (mapState[y][x][0]!= i) continue;

			int ny = y + dy[d];
			int nx = x + dx[d];

			if (ny > 0 && nx > 0 && ny <=N && nx <= N)
				moveChess(y,x,ny,nx,map[ny][nx], i);
			else moveChess(y,x,ny,nx,BLUE,i);

			vaild = vaildState();
			if (!vaild) break;
		}
		cnt++;
		if (!vaild) break;
	}
	return cnt;
}
void input() {
	cin >> N >> K;
	map = vector<vector<int>>(N+1, vector<int>(N+1));
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> map[i][j];
	for (int i = 0; i < K; i++) {
		int y, x, dir;
		cin >> y >> x >> dir;
		chess[i].y = y;
		chess[i].x = x;
		chess[i].dir = dir;
		mapState[y][x].push_back(i);
	}
}
int main() {
	input();
	cout << solution() << endl;
	return 0;
}

[알고리즘 문제 풀이][파이썬] 백준 10809번: 알파벳 찾기
[DB] 군대로 알아보는 트랜잭션 - 1. 원자성 편

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage