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

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

17837번: 새로운 게임 2

삼성 SW 역량테스트 문제입니다.

문제 조건

출력 예시

까다로운 구현 문제였습니다.

게임이 멈추는 경우는 3가지입니다.

1. 턴이 1000번보다 넘게 진행되었을 경우   -> -1를 출력

2. 게임을 진행해도 끝낼수 없는 경우         -> -1를 출력

3. 블럭을 움직였을때 4개 이상의 블럭이 쌓였을 경우  -> 턴 횟수를 출력

 

3번 경우가 있기 때문에, vector를 통해서, (X , Y) 좌표에 어느 블럭이 쌓여있는지를 저장했습니다.

 

블럭이 움직이는 경우는 4가지입니다.

1. 하얀색 칸에 도달했을 경우               -> X번 블럭부터 해당 칸으로 이동한다.

ex) 1 2 3 4 5        ->       1 2 / 3 4 5       (3번을 움직일 경우)

2. 빨간색 칸에 도달했을 경우               -> X번 블럭부터 거꾸로 해당 칸으로 이동한다.

ex) 1 2 3 4 5        ->       1 2 / 5 4 3       (3번을 움직일 경우)

3. 파란색 칸에 도달했을 경우               -> 방향을 바꾼뒤, 1번 혹은 2번 경우를 실행한다.

4. 움직인 곳이 map의 범위 밖일 경우    -> 3번 경우와 같다.

 

 

1. 게임이 끝나는 경우 중 -1를 출력하는 경우

////////////// solve 함수 중 /////////////////	
    if (ans > 1000) {
		cout << "-1";
        break;
	}
/////////////////////////////////////////////
        
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;
}

ans 변수의 의미는 턴이 진행된 횟수입니다. 

턴이 1000번보다 많이 진행됐을때, -1를 출력하고 break 했습니다.

 

first_map vector는 처음 블럭의 위치를 가지고 있습니다.

현재 쌓여있는 블럭을 나타내는 many_block 과 first_map이 같은 경우 1를 return했습니다.

 

 

2. 게임이 끝나는 경우 중 턴을 출력하는 경우

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;
}

한 좌표에서 블럭이 4개 이상 쌓여있으면 턴을 출력합니다. 조건에 따라 해당 경우 1을 return 했습니다.

 

 

3. 블럭의 움직임 구현 - 하얀색 칸

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();
	int start = 0;
	for (int i = 0; i < Size; i++) {
		if (num == many_block[x1][y1][i]) {
			start = i;
			break;
		}
	}
	for (int i = start; 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 = start; i < Size; i++) {
		many_block[x1][y1].pop_back();
	}
}

X번 블럭 위로 모든 블럭을 (x ,y)로 옮기는 역할을 합니다.

X번 블럭이 자신의 좌표에서 몇번째에 위치하는지를 먼저 확인합니다. -> start 변수

start부터 블럭이 쌓여있는 수까지 다음 좌표로 블럭을 계속 옮겨줍니다.

블럭을 다 옮긴후, 해당 블럭들을 빼야하니 pop_back()을 해줍니다.

 

 

4. 블럭의 움직임 구현 - 빨간색

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();
	int start = 0;
	for (int i = 0; i < Size; i++) {
		if (num == many_block[x1][y1][i]) {
			start = i;
			break;
		}
	}
	for (int i = Size - 1; i >= start; 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 = start; i < Size; i++) {
		many_block[x1][y1].pop_back();
	}
}

X번 블럭 위로 모든 블럭을 (x ,y)로 거꾸로 옮기는 역할을 합니다.

X번 블럭이 자신의 좌표에서 몇번째에 위치하는지를 먼저 확인합니다. -> start 변수

블럭이 쌓여있는 수부터 start까지 다음 좌표로 블럭을 계속 옮겨줍니다.

블럭을 다 옮긴후, 해당 블럭들을 빼야하니 pop_back()을 해줍니다.

 

 

문제 접근 방법

1. 입력받은 블럭의 위치를 저장한다.

2. 1번 블럭부터 K번 블럭까지 순서대로 블럭을 움직여준다.

   2-1. 블럭의 다음 좌표가 map 범위안일 경우 -> 하얀색, 빨간색, 파란색의 경우에 따라 움직여줍니다.

   2-2. 블럭의 다음 좌표가 map 범위밖일 경우 -> 파란색의 경우와 같이 해줍니다.

3. 블럭이 움직일 때마다 게임이 끝날 수 있는지를 확인합니다.(4개 이상 쌓이는가?)

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();
	int start = 0;
	for (int i = 0; i < Size; i++) {
		if (num == many_block[x1][y1][i]) {
			start = i;
			break;
		}
	}
	for (int i = start; 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 = start; 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();
	int start = 0;
	for (int i = 0; i < Size; i++) {
		if (num == many_block[x1][y1][i]) {
			start = i;
			break;
		}
	}
	for (int i = Size - 1; i >= start; 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 = start; i < Size; i++) {
		many_block[x1][y1].pop_back();
	}
}

void move_block(int x) {
	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;
}

 

 

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