[Programmers] 크레인 인형뽑기 게임(C++)

I 문제 소개

---

문제 설명

게임개발자인 죠르디는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다.
죠르디는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.

 

게임 화면은 1 x 1 크기의 칸들로 이루어진 N x N 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 5 x 5 크기의 예시입니다).
각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다.
모든 인형은 1 x 1 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다.
게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다.
집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다.
다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.

 

만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.

 

크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다.
(그림에서는 화면표시 제약으로 5칸만으로 표현하였음)

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한 사항

- board 배열은 2차원 배열로 크기는 5 x 5 이상 30 x 30 이하입니다.
- board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
- 0은 빈 칸을 나타냅니다.
- 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
- moves 배열의 크기는 1 이상 1,000 이하입니다.
- moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

---

II 문제 풀이

2019년 카카오 개발자 겨울 인턴십에서 출제된 문제라고 한다.

문제가 길어서 이해하는 데 조금 걸렸지만, 요약하자면 2차원 인형뽑기를 하는데 같은 인형이 쌓이면 터뜨려서 점수를 쌓는 것 같다.

 

알고리즘을 설계하자면,

0. 게임판인 2차원 배열 board와 명령인 1차원 배열 move, 인형을 뽑아서 담을 1차원 배열 basket
1. move에서 m이라는 명령이 들어왔을 때, m번째 열의 제일 위는 몇 행인지 저장해놓을 1차원 배열 top 생성
2. m의 명령에 따라 board[top][m]을 basket으로 push_back
  2-1. board[top][m]은 basket으로 옮겼으므로 0을 저장
  2-2. top은 한 칸 아래를 가리켜야하므로 top+=1 해줌
3. basket 배열을 순차적으로 탐색하면서 터뜨리며(pop 또는 erase) 점수 계산

2에서 basket.push_back을 수행할 때 3을 동시에 한다면 좀 더 시간을 단축할 수 있겠으나,

짜다보니 신경써야할게 점점 많아져서 처음에는 따로 짜고, 시간 초과가 뜬다면 여기서 줄일 심산이었다.

 

 

1. 초기 환경 설정 : 변수 및 top 배열 생성

---

배열들은 전부 vector로 만들었다. 게임판의 크기가 정해져있지도 않고 C++의 특징을 이용하기 위해서!

int solution(vector<vector<int>> board, vector<int> moves) {
	int answer = 0; // 답, 인형 점수
	vector<int> basket; // 인형을 뽑아서 담는 바구니
	vector<int> top; // 게임판에서 각 열의 가장 윗행을 가리키게 만들 예정
	int boardSize = board.size(); // NxN 배열의 N. 자주 쓸 것 같아 계산 시간 단축을 위해 미리 구해놓기
	int i, j, crane, target; // 밑에서 쓸 변수들
}

 

초기 환경에서 board만 주어지면 바로 만들 수 있는 top부터 만들어보았다.

for (i = 0;i < boardSize;i++)
	top.push_back(-1);

for (i = 0;i < boardSize;i++)
	for (j = 0;j < boardSize;j++)
		if (top[i]==-1 && board[j][i] != 0)
			top[i] = j;

 

 

 

꼭대기인지 판단하는 방법은 순차적으로 탐색하는데, 그 열에서 값이 0이 아닌 가장 먼저 도착한 행을 꼭대기로 했다.

가장 먼저 도착했는지를 알기 위해서 문제 특성상 나올 수 없는 값인 -1로 미리 초기화를 시켜주고 진행했다.

 

2. 인형 옮기기

---

moves 배열을 순차적으로 탐색하면서 명령을 실행시켰다.

주의할 점은 1열을 탐색하는 명령으로 2가 들어온다는 점이다. (배열은 0번째부터지만, 명령은 1번째부터다)

for (i = 0;i < moves.size();i++)
	{
		target = moves[i] - 1; // 배열은 0번째부터
		crane = board[top[target]][target]; // target열 top행의 인형값
		if (crane != 0) // 만약 target열이 빈 행이면 굳이 인형을 옮길 일이 없다
		{
			basket.push_back(crane); // 인형값을 basket에 추가
			board[top[target]][target] = 0; // 인형이 있던 자리는 빈자리(0)로 만듦
			if(top[target]+1<=boardSize-1)
				top[target]++; // 인형을 옮겨서 top이 빈자리가 됐으니 한 칸 아래(배열로는 ++)를 가리키게 함
		}
	}

아래쪽에 주석이 달리지 않은 조건문(if)은 top을 한 칸 아래로 옮기는 데, 밑바닥이면 옮기지 않아도 되니 추가했다.

 

3. 점수 계산

---

basket에 { 4, 3, 1, 1, 3, 2, 4 }와 같은 형태로 인형이 쌓였을 것이다.

순차 탐색해 1 두 개가 반복되니 두 개를 erase해주고 그러면 3이 또 반복되니 다시 탐색해서 또 erase해줘야 한다.

int sw;
while (1)
{
	sw = 0;
	for (i = 1;i < basket.size();i++) // i와 i-1을 비교할 것이므로 1부터 시작 (벡터 범위 초과 예방)
	{
		if (basket[i] == basket[i - 1])
		{
			basket.erase(basket.begin()+i);
			basket.erase(basket.begin()+i-1);
			answer += 2; // 한 번에 인형이 두 개씩 터지기 때문에 2점씩 추가해준다
			sw = 1;
		}
	}
	if (sw == 0)
		break;
}

sw의 역할은 한 번 탐색했을 때 터진 인형이 있다면 앞서 말했던 경우처럼 중간이 없어져서 반복이 돼버릴 수 있으므로 터질 때 sw를 1이 되게 만들어 탐색 이후 sw가 1이라면 다시 탐색하게 하는 스위치다.

 

이렇게 해서 제출하니 시간 초과 없이 모든 테스트 케이스에 통과했다.

그렇다하더라도 최악의 상황으로 반복될 수 있는 3의 과정을 아예 생략하고 싶어서 2에서 인형을 옮길 때 한꺼번에 처리하게도 만들어보았다. 그래서 최종적인 solution()은 다음과 같다.

 

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

int solution(vector<vector<int>> board, vector<int> moves) {
	/* 환경 설정 */
	int answer = 0;
	vector<int> basket;
	vector<int> top;
	int boardSize = board.size();
	int i, j, crane, target;

	/* top 생성 */
	for (i = 0;i < boardSize;i++)
		top.push_back(-1);
	for (i = 0;i < boardSize;i++)
		for (j = 0;j < boardSize;j++)
			if (top[i]==-1 && board[j][i] != 0)
				top[i] = j;

	/* 명령 실행 */
	for (i = 0;i < moves.size();i++)
	{
		target = moves[i] - 1;
		crane = board[top[target]][target];
		if (crane != 0)
		{
			basket.push_back(crane);
			if (basket.size() >= 2 && basket[basket.size() - 2] == crane)
			{
				basket.pop_back();
				basket.pop_back();
				answer += 2;
			}
			board[top[target]][target] = 0;
			if(top[target]+1<=boardSize-1)
				top[target]++;
		}
	}
	return answer;
}

 

사실 인형이 똑같은게 쌓인다는 걸 push_back을 수행하지 않아도 충분히 판단할 수 있는데, 그 부분까지는 부등호나 따질게 많아지니 귀찮아서 하지 않았다.

 

 

 

III 느낀점

---

풀고보니 문제의 길이에 비해 생각보다 단순한 문제였다.

알고리즘을 짜는 데에도 별로 시간이 걸리지 않았는데,

부등호에서 등호의 유무와 방향이나 벡터의 크기를 초과해서 참조하지는 않는지를 따지는 데에 시간이 꽤 걸렸다.

조금 더 디테일하게 코드를 짤 필요가 있겠다.

 

 

 

 

 

 

 

 

 

 

Coding Space by MIR :

카카오 개발자 인턴십

Programmers 크레인 인형뽑기 게임 C++

프로그래머스 크레인 인형뽑기 게임 C++