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

1. 문제 링크

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

17837번: 새로운 게임 2

2. 문제 개요

 말이 N마리 있다. 맵이 있는데 각 자리는 흰색, 빨간색, 파란색으로 구성되어 있다.

 매 턴마다 1번부터 N번까지의 말을 조건에 맞게 이동시킨다.

 쌓여있는 말 중 중간의 말이 선택되면 그 말의 위만 이동시킨다.

 흰색자리는 그대로, 빨간색 자리는 반대방향으로, 파란색 자리는 방향을 바꾸고 1칸을 이동한다.

 맵의 바깥은 파란색 자리의 규칙과 동일하다.

 

3. 문제 힌트

   특별한 알고리즘을 요구하지는않는다. 어떻게 자료구조를 설계하는지 , 문제에 적힌 순서와 조건을 어떻게 코드로 잘 옮기느냐에 달려있다고 생각한다. 

 

4. 문제 풀기

 

(1) 말의 자료구조

 말의 자료구조는 (x, y ,방향)에 속도를 향상하기 위한(번호, 앞 말 번호, 뒤 말 번호)를 추가하여 6가지의 정보로 이루어져 있다.

 -> 매 턴, 맵을 탐색 하면서( O(n^2)) 몇 번째 자리에 쌓여있는지 탐색(O(n))하는 것이 시간낭비라고 생각했기 때문에 번호정보를 자료구조에 추가했다. 이 문제에서 전자처럼 시간을 많이 써가면서 탐색하면 코드는 간단해지고 디버깅하는데 속도가 빨라진다는 장점은 있다고 생각한다. 하지만 시간 향상을 위해 자료구조가 복잡해지면 에러 발생률도 높고 코드도 길어지는 단점도 있다고 생각한다.

 

(2) 필요한 변수

 (2.1) 맵 탐색 없이 말의 위치를 바로 알 수 있게 말을 관리하는 배열이 필요하다. horse vector를 사용하였다. ( 배열 써도 상관없음 )

 (2.2) 맵 바닥 색깔을 구별할 수 있는 맵 배열.

 (2.3) 맵에 쌓여있는 말을 나타내기 위한 맵 vector.

 (2.4) 그 외 자잘한 지역변수

 

(3) 알고리즘

 딱히 알고리즘이라 할 것도 없다.

 실행 흐름을 보면 

 말을 찾는다. -> 말을 든다 -> 다음 땅을 확인한다 -> 조건에 맞게 놓는다 -> 4개 이상인가? -> 반복

 이 큰 틀이다.

 

 말을 자료구조 중 추가 정보를 사용하여 찾고, 지역변수 deque를 사용하여 들어 올린다(push). 그리고 땅의 색깔을 확인하고 조건에 맞게 연결 순서를 바꾼 뒤 deque에서 놓는다(pop)한다.

deque가 실제 손의 역할을 한다고 생각하면 된다!.

 

 

5. 코드

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

struct node {
	int num;
	int y, x, dir;
	int pre, post;
};
const int dx[] = { 0,1,-1,0,0 };
const int dy[] = { 0,0,0,-1,1 };

int n, k;
int map[12][12];
vector<node> horse;
vector<int> v[12][12];

int main()
{
	cin >> n >> k;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			cin >> map[i][j];

	for (int i = 0; i < k; ++i)
	{
		node temp;
		cin >> temp.y >> temp.x >> temp.dir;
		temp.post = temp.pre = -1;
		temp.y--; temp.x--;
		temp.num = i;

		horse.push_back(temp);
		v[temp.y][temp.x].push_back(i);
	}

	bool flag = false;

	int t = 1;

	while (t<=1000)
	{
		for (int i = 0; i < k; ++i)
		{
			//움직일 자리 확인.
			node next;
			next.y = horse[i].y + dy[horse[i].dir];
			next.x = horse[i].x + dx[horse[i].dir];

			//다음 자리가 맵 밖이라면 
			if (next.x < 0 || next.y < 0 || next.x >= n || next.y >= n)
			{
				if (horse[i].dir == 1)
					horse[i].dir = 2;
				else if (horse[i].dir == 2)
					horse[i].dir = 1;
				else if (horse[i].dir == 3)
					horse[i].dir = 4;
				else
					horse[i].dir = 3;

				int fixnx = horse[i].x + dx[horse[i].dir];
				int fixny = horse[i].y + dy[horse[i].dir];
				
				//밖이라서 뒤로가는데 또 파란색이면 멈춤
				if (map[fixny][fixnx] == 2)
					continue;
				else
				{
					//파란색이 아니면 이동
					next.y = fixny;
					next.x = fixnx;
				}
			}
			
			//움직일 말들 들어올릴 큐
			deque<node> dq;

			//맨 밑에 있는 말이라면
			if (horse[i].pre != -1)
			{
				horse[horse[i].pre].post = -1;
				horse[i].pre = -1;
			}

			//중간에 있는 말
			int count = 0;
			int nexthorse = i;
			while (nexthorse != -1)
			{
				count++;
				dq.push_back(horse[nexthorse]);
				nexthorse = horse[nexthorse].post;
			}
			for(int j=0;j<count;++j)
				v[horse[i].y][horse[i].x].pop_back();

			//다음 가는곳이 흰색이라면
			if (map[next.y][next.x] == 0)
			{
				//다음 장소의 말 갯수.
				int len = v[next.y][next.x].size();

				//말이 존재한다면 위에 얹기.
				if (len != 0)
				{
					//상호연결
					horse[v[next.y][next.x][len - 1]].post = i;
					dq[0].pre = v[next.y][next.x][len - 1];
				}

				//큐에 있는 모든것을 그 뒤에 얹음.
				while (!dq.empty())
				{
					node temp;
					temp = dq.front();
					dq.pop_front();

					temp.y = next.y;
					temp.x = next.x;

					horse[temp.num] = temp;

					v[temp.y][temp.x].push_back(temp.num);
				}
			}
			else if (map[next.y][next.x] == 1)
			{//빨간색이라면 얹을때 반대순서로 얹기만하면됨.
				int len = v[next.y][next.x].size();

				//앞 뒤 순서관계를 바꾸고
				for (int j = 0; j < dq.size(); ++j)
				{
					int temp;
					temp = dq[j].post;
					dq[j].post = dq[j].pre;
					dq[j].pre = temp;
				}

				//큐에서 나갈때 역순으로 나가면 됨.
				if (len != 0)
				{
					horse[v[next.y][next.x][len - 1]].post = dq.back().num;

					dq[dq.size()-1].pre = v[next.y][next.x][len - 1];
				}

				while (!dq.empty())
				{
					node temp;
					temp = dq.back();
					dq.pop_back();

					temp.y = next.y;
					temp.x = next.x;

					horse[temp.num] = temp;
					
					v[temp.y][temp.x].push_back(temp.num);
				}
			}
			else
			{
				//파란색이면, 반대방향으로 가야한다.
				//그 반대방향이 또 파란색이거나, 맵의 바깥이면 추가 조작을 함.
				int fixdir;

				if (horse[i].dir == 1)
					fixdir = 2;
				else if (horse[i].dir == 2)
					fixdir = 1;
				else if (horse[i].dir == 3)
					fixdir = 4;
				else
					fixdir = 3;

				//반대방향으로 수정된 다음장소
				int fixnx = horse[i].x + dx[fixdir];
				int fixny = horse[i].y + dy[fixdir];
			
				//갈 수 있는장소라면 흰색과 마찬가지로 이동하기.
				if (fixnx < 0 || fixny < 0 || fixnx >= n || fixny >= n || map[fixny][fixnx] == 2)
				{
					dq[0].dir = fixdir;

					int len = v[horse[i].y][horse[i].x].size();

					if (len != 0)
					{
						horse[v[horse[i].y][horse[i].x][len - 1]].post = i;
						dq[0].pre = v[horse[i].y][horse[i].x][len - 1];
					}

					while (!dq.empty())
					{
						node temp;
						temp = dq.front();
						dq.pop_front();

						horse[temp.num] = temp;

						v[temp.y][temp.x].push_back(temp.num);
					}
				}
				else
				{
					//갈 수 없는장소라면, 들었던것(큐에있는것) 다시 놓기.
					dq[0].dir = fixdir;
					int len = v[horse[i].y][horse[i].x].size();

					if (len != 0)
					{
						horse[v[horse[i].y][horse[i].x][len - 1]].post = i;
						dq[0].pre = v[horse[i].y][horse[i].x][len - 1];
					}

					while (!dq.empty())
					{
						node temp;
						temp = dq.front();
						dq.pop_front();

						horse[temp.num] = temp;

						v[temp.y][temp.x].push_back(temp.num);
					}
					i--;
					continue;
				}
			}
			//종료조건을 만족하는지. 각 말이 움직일때마다 체크.
			if (v[horse[i].y][horse[i].x].size() >= 4)
			{
				flag = true;
				break;
			}

		}
		//종료조건을 만족했는지.
		if (flag)
			break;
		t++;
	}

	if (flag)
		cout << t;
	else
		cout << "-1";
	

	return 0;
}

6. 결과 사진

지적, 댓글 언제나 환영입니다~