백준 17780 - 새로운 게임(C++)

문제 링크입니다. https://www.acmicpc.net/problem/17780

17780번: 새로운 게임

구현 능력을 물어보는 문제였습니다. 

문제 조건

출력 예시

블럭을 조건에 따라 움직였을때 어느턴에서 끝나는지를 물어보는 문제입니다.

 

1. 블럭이 움직이는 조건(움직이려는 블럭이 맨 밑에 있을 경우에만 이동이 가능합니다)

   1-1. 흰색칸일 경우 -> 해당 칸으로 이동합니다. 이미 말이 있는 경우는 X번 말 위의 말이 모두 이동합니다.

   ex) 1 2 3 4 5 -> 1 2 / 3 4 5

   1-2. 빨간칸일 경우 -> 해당 칸으로 거꾸로 이동합니다. 이미 말이 있는 경우 X번 말부터 거꾸로 이동합니다.

   ex) 1 2 3 4 5 -> 1 2 / 5 4 3 

   1-3. 파란칸이거나 이동할 수 없는 경우 -> 이동 방향을 바꿉니다. 이때 도착한 곳이 흰색이나 빨간칸에 이동합니다.

 

2. 게임이 끝나는 조건

   2-1. 블럭이 움직일 때마다 어느 한칸에 4개 이상의 블럭이 쌓이면 게임이 끝난뒤 턴의 횟수를 출력합니다.

   2-2. 턴이 1000번 초과일 경우 -1를 출력하고 게임을 끝냅니다.

   2-3. 게임이 종료되지 않는 경우 -1를 출력하고 게임을 끝냅니다.

 

 

0. 사용된 배열과 백터에 대한 설명

int map[13][13];   // 0 - 흰색, 1 - 빨간색, 2 - 파란색
vector<int> first_map[13][13];
vector<int> many_block[13][13];

map 배열은 해당칸이 어떤 색인지를 저장하는 배열입니다.

first_map 백터는 처음 블럭의 위치를 저장하는 백터입니다. -> 게임이 끝나는 경우를 구할 때 사용됩니다.

many_block 백터는 블럭이 이동할때마다 (X , Y)칸에 어느 블럭이 쌓여있는지를 저장하는 백터입니다.

 

 

1. 블럭이 움직이는 조건 구현하기 - 흰색칸

void white_space(int x, int y, int num) {
	int x1 = block[num].row, y1 = block[num].col;
	int Size = many_block[x1][y1].size();
	for (int i = 0; i < Size; i++) {
		int X = many_block[x1][y1][i];
		many_block[x][y].push_back(X);
		block[X] = { x,y,block[X].way };
	}
	for (int i = 0; i < Size; i++) {
		many_block[x1][y1].pop_back();
	}
}

움직이려는 블럭이 맨 밑의 블럭일 경우에만 해당 함수를 실행합니다.

자기 위의 블럭을 모두 움직이면 됨으로 이동하려는 칸에 저장된 값들을 모두 넣어줍니다.

이동한 뒤 전에 있던 칸에는 블럭이 없음으로 모두 pop해줍니다.

 

 

2. 블럭의 움직이는 조건 구현하기 - 빨간칸

void red_space(int x, int y, int num) {
	int x1 = block[num].row, y1 = block[num].col;
	int Size = many_block[x1][y1].size();
	for (int i = Size - 1; i >= 0; i--) {
		int X = many_block[x1][y1][i];
		many_block[x][y].push_back(X);
		block[X] = { x,y,block[X].way };
	}
	for (int i = 0; i < Size; i++) {
		many_block[x1][y1].pop_back();
	}
}

다음칸에 자기 위의 블럭부터 거꾸로 집어넣습니다.

블럭을 넣었다면 전의 칸은 블럭이 없어짐으로 pop을 해줬습니다.

 

 

3. 블럭의 움직이는 조건 구현하기 - 파란색 + 벗어날 경우

/////////////////////////////////move_block 함수 중////////////////////////////////////////			
                block[x].way = change_way(block[x].way);
				xx = block[x].row + dx[block[x].way];
				yy = block[x].col + dy[block[x].way];
				if (xx >= 1 && xx <= N && yy >= 1 && yy <= N) {
					if (map[xx][yy] == 0) {
						white_space(xx, yy, x);
					}
					else if (map[xx][yy] == 1) {
						red_space(xx, yy, x);
					}
				}
///////////////////////////////////////////////////////////////////////////////////////////

먼저 방향을 바꾸어 줍니다.

바꾼 방향으로 이동했을때, 움직인 곳이 좌표 안이며, 흰칸이거나 빨간칸일 경우에 해당 작업을 수행합니다.

 

 

4. 게임이 끝나는 조건

//////////////////////////solve 함수 중//////////////////////////////////////
		if (ans > 1000) {
			cout << "-1";
			break;
		}
////////////////////////////////////////////////////////////////////////////
bool game_finish() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (many_block[i][j].size() >= 4) return 1;
		}
	}
	return 0;
}
bool check_first() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (many_block[i][j] != first_map[i][j]) return 0;
		}
	}
	return 1;
}

먼저 턴이 1000번보다 많이 진행되었을 경우 게임을 종료합니다.

어느 한 블럭이라도 4개 이상의 블럭이 쌓여있다면 게임을 종료합니다.

게임이 끝날 수 없다면 게임을 종료합니다 -> 처음 블럭의 위치와 같아진다면으로 해석 가능합니다.

 

 

문제 접근 방법

1. 블럭의 상태를 입력받고, 해당 블럭의 위치에 저장한다.

2. 블럭을 1번부터 K번까지 움직인다.

3. 게임이 끝나는지는 확인한다.

4. 조건에 따라 결과값을 출력한다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>

using namespace std;

int N, K;
int map[13][13];   // 0 - 흰색, 1 - 빨간색, 2 - 파란색
vector<int> first_map[13][13];
vector<int> many_block[13][13];
typedef struct bk {
	int row;
	int col;
	int way;
}bk;
bk block[11];
int dx[5] = { 0,0,0,-1,1 }; // 그대로, 오, 왼, 상, 하
int dy[5] = { 0,1,-1,0,0 };

int change_way(int x) {
	if (x == 1 || x == 3) return x + 1;
	else return x - 1;
}

bool game_finish() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (many_block[i][j].size() >= 4) return 1;
		}
	}
	return 0;
}

void white_space(int x, int y, int num) {
	int x1 = block[num].row, y1 = block[num].col;
	int Size = many_block[x1][y1].size();
	for (int i = 0; i < Size; i++) {
		int X = many_block[x1][y1][i];
		many_block[x][y].push_back(X);
		block[X] = { x,y,block[X].way };
	}
	for (int i = 0; i < Size; i++) {
		many_block[x1][y1].pop_back();
	}
}

void red_space(int x, int y, int num) {
	int x1 = block[num].row, y1 = block[num].col;
	int Size = many_block[x1][y1].size();
	for (int i = Size - 1; i >= 0; i--) {
		int X = many_block[x1][y1][i];
		many_block[x][y].push_back(X);
		block[X] = { x,y,block[X].way };
	}
	for (int i = 0; i < Size; i++) {
		many_block[x1][y1].pop_back();
	}
}

void move_block(int x) {
	int start = 0;
	int x1 = block[x].row, y1 = block[x].col;
	for (int i = 0; i < many_block[x1][y1].size(); i++) {
		if (x == many_block[x1][y1][i]) {
			start = i;
			break;
		}
	}
	if (start == 0) {
		int xx = block[x].row + dx[block[x].way];
		int yy = block[x].col + dy[block[x].way];
		if (xx >= 1 && xx <= N && yy >= 1 && yy <= N) {
			if (map[xx][yy] == 0) {
				white_space(xx, yy, x);
			}
			else if (map[xx][yy] == 1) {
				red_space(xx, yy, x);
			}
			else {
				block[x].way = change_way(block[x].way);
				xx = block[x].row + dx[block[x].way];
				yy = block[x].col + dy[block[x].way];
				if (xx >= 1 && xx <= N && yy >= 1 && yy <= N) {
					if (map[xx][yy] == 0) {
						white_space(xx, yy, x);
					}
					else if (map[xx][yy] == 1) {
						red_space(xx, yy, x);
					}
				}
			}
		}
		else {
			block[x].way = change_way(block[x].way);
			xx = block[x].row + dx[block[x].way];
			yy = block[x].col + dy[block[x].way];
			if (xx >= 1 && xx <= N && yy >= 1 && yy <= N) {
				if (map[xx][yy] == 0) {
					white_space(xx, yy, x);
				}
				else if (map[xx][yy] == 1) {
					red_space(xx, yy, x);
				}
			}
		}
	}
}

bool check_first() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (many_block[i][j] != first_map[i][j]) return 0;
		}
	}
	return 1;
}

void solve() {
	int ans = 1;
	while (1) {
		if (ans > 1000) {
			cout << "-1";
			break;
		}
		if (check_first() && ans > 1) {
			cout << "-1";
			break;
		}
		for (int i = 1; i <= K; i++) {
			move_block(i);
			if (game_finish()) {
				cout << ans;
				return;
			}
		}
		ans++;
	}
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	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 >> block[i].row >> block[i].col >> block[i].way;
		many_block[block[i].row][block[i].col].push_back(i);
		first_map[block[i].row][block[i].col].push_back(i);
	}
	solve();
	return 0;
}

 

질문 및 조언 댓글 남겨주세요!