[0x0D] 시뮬레이션

BFS, DFS 등의 자료구조처럼 정형화 되어있지 않아서 어렵다.

 

연습 문제

 

15683: 감시

#include <iostream>
#include <vector>

using namespace std;

int n, m;
int office[10][10];
vector<pair<int, int>> cameras;
int answer = 9999;

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

void upd(int k, int dir, vector<pair<int, int>>& v)
{
	dir %= 4;
	int nx, ny;
	nx = cameras[k].first + dx[dir];
	ny = cameras[k].second + dy[dir];

	while (nx >= 0 && nx < n && ny >= 0 && ny < m)
	{
		if (office[nx][ny] == 6)
		{
			return;
		}
		if (office[nx][ny] == 0)
		{
			office[nx][ny] = -1;
			v.push_back({ nx, ny });
		}

		nx += dx[dir];
		ny += dy[dir];
	}
}

void init_table(vector<pair<int, int>>& v)
{
	while (!v.empty())
	{
		office[v.back().first][v.back().second] = 0;
		v.pop_back();
	}
}

void backtracking(int k)
{
	if (k == cameras.size())
	{
		int s = 0;
		for (int x = 0; x < n; ++x)
		{
			for (int y = 0; y < m; ++y)
			{
				if (!office[x][y])
				{
					s++;
				}
			}
		}
		answer = (answer < s) ? answer : s;
		return;
	}

	for (int i = 0; i < 4; ++i)
	{
		int cx, cy;
		cx = cameras[k].first;
		cy = cameras[k].second;

		vector<pair<int, int>> v;

		// 현재 카메라 좌표에서 카메라 타입에 따라 감시구역 설정
		if (office[cx][cy] == 1)
		{
			upd(k, i, v);
		}
		else if (office[cx][cy] == 2)
		{
			upd(k, i, v);
			upd(k, i + 2, v);
		}
		else if (office[cx][cy] == 3)
		{
			upd(k, i, v);
			upd(k, i + 1, v);
		}
		else if (office[cx][cy] == 4)
		{
			upd(k, i, v);
			upd(k, i + 1, v);
			upd(k, i + 2, v);
		}
		else if (office[cx][cy] == 5)
		{
			upd(k, i, v);
			upd(k, i + 1, v);
			upd(k, i + 2, v);
			upd(k, i + 3, v);
		}

		backtracking(k + 1);
		init_table(v);
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	// 세로크기n 가로크기m
	cin >> n >> m;

	for (int x = 0; x < n; ++x)
	{
		for (int y = 0; y < m; ++y)
		{
			cin >> office[x][y];
			if (office[x][y] >= 1 && office[x][y] <= 5)
			{
				cameras.push_back({ x, y });
			}
		}
	}

	backtracking(0);

	cout << answer;

	return 0;
}

 

upd 함수와 4진법의 접근이 핵심이다.

자잘한 부분들은 어느정도 떠올렸는데 udp를 어떻게 구현할지 도무지 감이 안잡혀서 결국 해답을 보고 참고해서 백트래킹으로 풀어냈다.

해답 코드는 백트래킹 대신 4ⁿ의 루프를 가지는 for문을 이용한다.

 

18808: 스티커 붙이기

#include <iostream>
#include <algorithm>

using namespace std;

int notebook[50][50];
int sticker[12][12];

int n, m, k;
int r, c;
int answer;

bool is_pastable(int& x, int& y)
{
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			if (x + i >= n || y + j >= m)
			{
				return false;
			}
			if (notebook[x + i][y + j] + sticker[i][j] == 2)
			{
				return false;
			}
		}
	}
	return true;
}

void paste(int& x, int& y)
{
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			if (sticker[i][j])
			{
				notebook[x + i][y + j] = 1;
			}
		}
	}
}

void rotate()
{
	int tmp[12][12] = {};

	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			tmp[i][j] = sticker[i][j];
		}
	}

	for (int i = 0; i < c; ++i)
	{
		for (int j = 0; j < r; ++j)
		{
			sticker[i][j] = tmp[r-j-1][i];
		}
	}
	swap(r, c);
}

void func(int& s)
{
	for (int i = 0; i < 4; ++i)
	{
		// 현재 노트에 붙일 수 있는가 판별
		for (int x = 0; x < n; ++x)
		{
			for (int y = 0; y < m; ++y)
			{
				if (is_pastable(x, y))
				{
					paste(x, y);
					answer += s;
					return;
				}
			}
		}
		rotate();
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	// n가로 m세로 스티커개수k

	cin >> n >> m >> k;

	for (int i = 0; i < k; ++i)
	{	// r행 c열

		cin >> r >> c;

		int s = 0;

		for (int x = 0; x < r; ++x)
		{
			for (int y = 0; y < c; ++y)
			{
				cin >> sticker[x][y];
				if (sticker[x][y])
				{
					s++;
				}
			}
		}
		func(s);
	}

	cout << answer;

	return 0;
}

 

이 문제도 사실상 해답을 보고 푼거나 마찬가지

스티커의 회전이 핵심이다.

처음에 문제 이해를 잘못해서 모든 스티커에 대한 완전 탐색을 구현하려고 해서 까마득 했음

그게 아니라 그냥 순서대로 붙이는거라서 어느정도의 풀이는 떠올림

 

12100: 2048 (Easy)

#include <iostream>
#include <vector>

using namespace std;

int n, answer;

int mx(vector<vector<int>>& v)
{
	int m = 0;

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			m = (v[i][j] > m) ? v[i][j] : m;
		}
	}
	return m;
}

vector<vector<int>> push_numbers(vector<vector<int>> v, int& dir)
{

	// 우측으로
	if (dir == 0)
	{
		for (int i = 0; i < n; ++i)
		{
			int t[101] = {};
			int idx = 0;

			for (int j = n - 1 ; j >= 0; --j)
			{
				if (v[i][j] == 0)
				{
					continue;
				}
				if (t[idx] == 0)
				{
					t[idx] = v[i][j];
				}
				else if (t[idx] == v[i][j])
				{
					t[idx++] *= 2;
				}
				else
				{
					t[++idx] = v[i][j];
				}
			}
			for (int j = 0; j < n; ++j)
			{
				v[i][j] = t[n-j-1];
			}
		}
	}

	// 위로
	else if (dir == 1)
	{
		for (int i = 0; i < n; ++i)
		{
			int t[101] = {};
			int idx = 0;

			for (int j = 0; j < n; ++j)
			{
				if (v[j][i] == 0)
				{
					continue;
				}
				if (t[idx] == 0)
				{
					t[idx] = v[j][i];
				}
				else if (t[idx] == v[j][i])
				{
					t[idx++] *= 2;
				}
				else
				{
					t[++idx] = v[j][i];
				}
			}
			for (int j = 0; j < n; ++j)
			{
				v[j][i] = t[j];
			}
		}
	}

	// 좌측으로
	else if (dir == 2)
	{
		for (int i = 0; i < n; ++i)
		{
			int t[101] = {};
			int idx = 0;

			for (int j = 0; j < n; ++j)
			{
				if (v[i][j] == 0)
				{
					continue;
				}
				if (t[idx] == 0)
				{
					t[idx] = v[i][j];
				}
				else if (t[idx] == v[i][j])
				{
					t[idx++] *= 2;
				}
				else
				{
					t[++idx] = v[i][j];
				}
			}
			for (int j = 0; j < n; ++j)
			{
				v[i][j] = t[j];
			}
		}
	}

	// 아래로
	else
	{
		for (int i = 0; i < n; ++i)
		{
			int t[101] = {};
			int idx = 0;

			for (int j = n-1; j >= 0; --j)
			{
				if (v[j][i] == 0)
				{
					continue;
				}
				if (t[idx] == 0)
				{
					t[idx] = v[j][i];
				}
				else if (t[idx] == v[j][i])
				{
					t[idx++] *= 2;
				}
				else
				{
					t[++idx] = v[j][i];
				}
			}
			for (int j = 0; j < n; ++j)
			{
				v[j][i] = t[n - j - 1];
			}
		}
	}
	return v;
}

void backtracking(int k, vector<vector<int>> v)
{
	if (k == 5)
	{
		int m = mx(v);
		answer = answer > m ? answer : m;
		return;
	}

	for (int i = 0; i < 4; ++i)
	{
		backtracking(k + 1, push_numbers(v, i));
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	vector<vector<int>> v2;

	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		vector<int> v1;
		for (int i = 0; i < n; ++i)
		{
			int t;
			cin >> t;
			v1.push_back(t);
		}
		v2.push_back(v1);
	}

	backtracking(0, v2);

	cout << answer;

	return 0;
}

 

어떻게든 2차원 벡터를 이용해서 풀어보고 싶어가지고 개고생을 했다.

핵심은 한쪽으로 숫자를 밀어넣는 부분이다. 전체적으로 보면 사실상 브루트포스이다.

구현문제들이 진짜 막막하다.

dfs, bfs, 백트래킹, 브루트포스가 섞여서 나오는데 돌아버릴것같음