이것 저것 &

문제링크: https://www.acmicpc.net/problem/13459

까다로운 문제였습니다. 10번까지 검증하기 때문에 dfs가 아니라 bfs로 구현해야 했습니다.

1. bfs와 while문을 사용하여 행동을 구현한다. 

    - 이동할 곳이 #이 아니고 현재있는 좌표가 O가 아니면 계속 이동하게끔 구현한다.

2.이동후 두좌표가 같을때를 확인해준다.

    - 경우는 2가지이다. 함께 O에 있을때, 한쪽 끝에 함께 몰려있을때  함께 O라면 실패이기 때문에 큐에 넣지않고 마무       리 한쪽 끝이라면 값을 비교해서 하나를 한칸뒤로 무른다. 

3. 매 반복마다 result값을 증가시킨다. (구슬 탈출2 에서 유효)

정답코드입니다.

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

int n = 0, m = 0;
char arr[12][12];

int r_y, r_x;
int b_y, b_x;
int result = 0;

int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1, -1, 0, 0 };
bool visited[12][12][12][12] = { 0, };

int bfs() {

	queue <pair <int, int>> b_que;
	queue <pair <int, int>> r_que;
	b_que.push(make_pair(b_y, b_x));
	r_que.push(make_pair(r_y, r_x));

	result = 0; // 0으로 초기화
	while (!b_que.empty()) {
		int sized = b_que.size();

		while (sized--) {
			int red_y = r_que.front().first;
			int red_x = r_que.front().second;
			int blue_y = b_que.front().first;
			int blue_x = b_que.front().second;
			r_que.pop(), b_que.pop();


			if (arr[red_y][red_x] == 'O') // O에 있을때
				return result;
			
			for (int i = 0; i < 4; i++) {
				int nextred_y = red_y;
				int nextred_x = red_x;
				int nextblue_y = blue_y;
				int nextblue_x = blue_x;

				while (arr[nextred_y + y_ar[i]][nextred_x + x_ar[i]] != '#' && arr[nextred_y][nextred_x] != 'O') {
					nextred_y += y_ar[i];
					nextred_x += x_ar[i];
				}
				while (arr[nextblue_y + y_ar[i]][nextblue_x + x_ar[i]] != '#' && arr[nextblue_y][nextblue_x] != 'O') {
					nextblue_y += y_ar[i];
					nextblue_x += x_ar[i];
				}
				if (nextred_y == nextblue_y && nextred_x == nextblue_x) {
					if (arr[nextred_y][nextred_x] == 'O') continue; // 이 경로는 가면 안되는 경로라서 continue로 넘겨줌 	

					// 더 많이 이동한쪽이 진짜 자기 위치  
					if ((abs(nextred_y - red_y) + abs(nextred_x - red_x)) > (abs(nextblue_y - blue_y) + abs(nextblue_x - blue_x)))
						nextred_y -= y_ar[i], nextred_x -= x_ar[i];
					else
						nextblue_y -= y_ar[i], nextblue_x -= x_ar[i];
						
				}

				if (visited[nextred_y][nextred_x][nextblue_y][nextblue_x]) continue; //기존에 방문했다면 
				r_que.push(make_pair(nextred_y,nextred_x));
				b_que.push(make_pair(nextblue_y,nextblue_x));
				visited[nextred_y][nextred_x][nextblue_y][nextblue_x] = 1;

			}


		}

		if (result == 10) return -1; 
		result++;
	}

	return -1;


}

int main() {

	ios_base::sync_with_stdio(0); 
	cin.tie(0);



	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'B')
				b_y = i, b_x = j, arr[i][j] = '.';
			else if (arr[i][j] == 'R')
				r_y = i, r_x = j, arr[i][j] = '.';
		}


	if (bfs() == -1)
		cout << 0 << endl;
	else
		cout << 1 << endl;


	
	return 0;
}

스스로 부족한 것을 많이 느꼈습니다. 구슬탈출2를 풀어보면서 더욱 연습할 계획입니다. 

아래는 dfs를 통해 구현한 코드입니다.

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int n, m;
string arr[10];
bool result = 0;
int y_ar[4] = { 0,1,0,-1 };
int x_ar[4] = { -1,0,1,0 };

void dfs(int cnt, int ry, int rx, int by, int bx) {
	if (cnt == 10)
		return;
	if (result)
		return;

	for (int i = 0; i < 4; i++) {

		int nry = ry, nrx = rx;
		int nby = by, nbx = bx;
		bool blue = false, red = false;
		while (1) {

			if (arr[nry + y_ar[i]][nrx + x_ar[i]] == '.') {
				nry += y_ar[i];
				nrx += x_ar[i];
			}
			else if (arr[nry + y_ar[i]][nrx + x_ar[i]] == 'O') {
				nry += y_ar[i];
				nrx += x_ar[i];
				red = true;
				break;
			}
			else if (arr[nry + y_ar[i]][nrx + x_ar[i]] == '#') {
				break;
			}
		}

		while (1) {
			if (arr[nby + y_ar[i]][nbx + x_ar[i]] == '.') {
				nby += y_ar[i];
				nbx += x_ar[i];
			}
			else if (arr[nby + y_ar[i]][nbx + x_ar[i]] == 'O') {
				nby += y_ar[i];
				nbx += x_ar[i];
				blue = true;
				break;
			}
			else if (arr[nby + y_ar[i]][nbx + x_ar[i]] == '#') {
				break;
			}
		}

		if (blue == true)
			continue;
		if (red == true) {
			result = true;
			return;
		}

		if (nrx == nbx && nry == nby) {			//포개진 경우
			if (i == 0) {
				if (rx > bx) 	nrx += 1;	//빨간공이 밑에 있었던 경우
				else			nbx += 1;
			}
			else if (i == 1) {
				if (ry > by)	nby -= 1;		//파란공이 더 왼쪽에서 시작한 경우
				else			nry -= 1;
			}
			else if (i == 2) {
				if (rx > bx)		nbx -= 1;		//파란공이 더 위에서 시작
				else				nrx -= 1;
			}
			else if (i == 3) {
				if (ry > by)		nry += 1;		//빨간공이 더 오른쪽에서 시작
				else				nby += 1;
			}
		}

		dfs(cnt + 1, nry, nrx, nby, nbx);




	}

}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;

	int ry, rx, by, bx;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 'R') {
				ry = i, rx = j;
				arr[i][j] = '.';
			}
			else if(arr[i][j] == 'B') {
				by = i, bx = j;
				arr[i][j] = '.';
			}
		}
	}

	dfs(0, ry, rx, by, bx);
	cout << result << endl;

	return 0;
}

문제링크:https://www.acmicpc.net/problem/16234

시뮬레이션 문제입니다.

아래 조건들을 만족시키며 진행해야 합니다. 

/*
국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
연합을 해체하고, 모든 국경선을 닫는다.
*/

알고리즘 입니다.

• 반복문을 통해서 각점들에서 dfs(혹은 bfs)를 통해서 인구이동이 가능한지 확인   
  - visited 사용(방문여부), sum(배열값 합), cnt 사용(배열 개수), vetor(방문 배열 좌표)
• dfs(혹은 bfs)후에 변경된 값들을 arr에 저장, 이때 cnt는 2보다 크거나 같아야한다.  bool값도 변경한다.
• bool값을 확인하고 반복문을 break할지 카운트값(result)을 올릴지 판단한다.

정답코드입니다.

#include <iostream>
#include <vector>
#include <cstring>
#include <math.h>
using namespace std;

int arr[51][51] = { 0 };
bool visited[51][51];

int n = 0, l = 0, r = 0;
int result = 0; 
int cnt, sum;
vector <pair <int, int>> vec;

//dfs 방향
int y_ar[4] = { 1,-1,0,0 };
int x_ar[4] = { 0,0,1,-1 };

void dfs(int yy, int xx) {

	for (int i = 0; i < 4; i++) {
		int y = yy + y_ar[i];
		int x = xx + x_ar[i];

		if (!visited[y][x]) {
			if (y >= 0 && y < n&&x >= 0 && x < n) {
				if (abs(arr[yy][xx] - arr[y][x]) >= l && abs(arr[yy][xx] - arr[y][x]) <= r) {
					visited[y][x] = 1;
					cnt++;
					sum += arr[y][x];
					vec.push_back(make_pair(y, x));
					dfs(y, x);
				}
			}
		}
	}
}


int main() {
	cin >> n >> l >> r;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> arr[i][j];

	while (1) {
		bool jud = false;
		memset(visited, 0, sizeof(visited));

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!visited[i][j]) {

					vec.clear();
					cnt = 1;
					sum = arr[i][j];
					visited[i][j] = 1;

					vec.push_back(make_pair(i,j));
					dfs(i, j);
					
					if (cnt >= 2) {
						jud = true;
						int aver_val = sum / cnt;
						for (int k = 0; k < vec.size(); k++) 
							arr[vec.at(k).first][vec.at(k).second] = aver_val;
						
					}

				}
			}
		}


		if (jud == false)
			break;
		else
			result++;


	}
	cout << result << endl;
}

문제링크: https://www.acmicpc.net/problem/16236

시뮬레이션 문제입니다. 상어가 먹이를 먹으면서 돌아다니는 시간을 출력하는 문제입니다.

• 1. bfs 를 통해서 도달할 수 있는 위치들의 최단거리를 표시합니다. 
• 2. 배열을 탐색(O(n))하면서 먹을수 있는 먹이이고 최단거리인 먹이를 선택합니다. 
• 3. 먹이를 선택할때에는 위에 있는 먹이, 왼쪽에 있는 먹이가 우선순위를 가지게 됩니다. 
• 4. 1~3번을 반복하며 상어가 이동할 수 있는 최대경로를 계산하고 먹을 먹이가 없는 시점에서의 값을 출력합니다. 

예외를 처리해주어야 하는게 상어 위치를 9로 만들어 두시게 되면은 만약 상어의 크기가 9보다 커지게 될때 bfs에서 계속 해당 위치를 탐색하며 무한루프에 빠질 수 있습니다. 그부분 조심하시고, 문제의 조건들을 꼼꼼하게 확인하시면 그렇게 어렵지 않은 문제였습니다.

정답코드입니다.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;


int n = 0, result = 0;
int sy, sx, ssize = 2, s_ex = 0;
int arr[21][21] = { 0 };
int visited[21][21];
int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };

void bfs() {

	queue <int> que[2];
	que[0].push(sy);
	que[1].push(sx);
	visited[sy][sx] = 1;
	while (que[0].empty() != 1) {
		int yy = que[0].front();
		int xx = que[1].front();

		que[0].pop(), que[1].pop();

		for (int i = 0; i < 4; i++) {
			int y = y_ar[i] + yy;
			int x = x_ar[i] + xx;

			if(x >=1 && x<=n && y>=1 && y <=n)
				if (visited[y][x] == 0 && arr[y][x] <= ssize) {
					visited[y][x] = visited[yy][xx] + 1;
					que[0].push(y);
					que[1].push(x);

				}
		}

	}
}

bool select_fish() {

	int len = (int)2e9;
	int select_y, select_x;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (visited[i][j] != 0 && visited[i][j] < len)
				if (ssize > arr[i][j] && arr[i][j] != 0)
					len = visited[i][j], select_y = i, select_x = j;

	if (len != (int)2e9) {

		// 물고기 자리 이동
		arr[sy][sx] = 0;
		sy = select_y;
		sx = select_x;
		arr[sy][sx] = 1000000000;
		result += len - 1;
		s_ex++;
		if (s_ex == ssize)
			s_ex = 0, ssize++;
		return true;
	}
	return false;

}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 9)
				sy = i, sx = j, arr[i][j] = 1000000000;

		}
	while (1) {
		bool jud=false;

		memset(visited, 0, sizeof(visited));
		bfs();

	
		jud = select_fish();
		if (jud == false)
			break;

	}

	cout << result << '\n';
	return 0;
}

문제링크:https://www.acmicpc.net/problem/11559

테트리스문제입니다. 테트리스를 구현,시뮬레이션 해야하는 문제입니다.

구현 능력을 보여주는데 적합하기 때문에 많은 코딩테스트에서 사용되는 단골 문제이기 때문에 꼭 연습하시길 추천 드립니다. 

정말 다양한 방법이 있습니다.  우선 탐색을 통해서 값을 얻어야 하는데 dfs, bfs 모두 상관없습니다. (여기서는 dfs가 코드가 짧고 가독성이 좋습니다.)

알고리즘은

• 1. 탐색을 통해서 없애야 하는 인덱스들을 표시한다. 
• 2. 없애야 하는 인덱스들을 없애고, 빈 칸들을 채워넣는다.
• 3. 없애야 하는 인덱스가 없을때 까지 반복한다.

주의 하실점은 연쇄로 터지는 것을 한번의 과정으로 본다는 것입니다. 

저는 vector를 사용하였고, dfs 두가지를 이용해서 구현하였습니다.

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
string val[12];
vector <char> arr[6];

int result = 0;
int x_ar[4] = { 1,-1,0,0 };
int y_ar[4] = { 0,0,1,-1 };
int visited[6][12] = { 0 };

void dfs2(char a, int yy, int xx,int cnt) {
	int sum = cnt;
	
	for (int i = 0; i < 4; i++) {
		int y = yy + y_ar[i];
		int x = xx + x_ar[i];
		if (y >= 0 && y < 6 && x >= 0 && x < 12 && arr[y][x] == arr[yy][xx] && visited[y][x] == 0) {
			sum++;
			visited[y][x] = sum;
			dfs2(a, y, x,sum );

		}
	}
}

void dfs(char a,int yy,int xx) {
	arr[yy][xx] = '8';
	visited[yy][xx] = -1;
	for (int i = 0; i < 4; i++) {
		int y = yy + y_ar[i];
		int x = xx + x_ar[i];
		if (y >= 0 && y < 6 && x >= 0 && x < 12 && arr[y][x] == a && visited[y][x] != -1) {
			dfs(a, y, x);
		
		}
	}
}

bool solve() {
	bool jud = false;
	
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 12; j++) {
			if (arr[i][j] != '.' ) {
				
				memset(visited, 0, sizeof(visited));
				visited[i][j] = 1;
				dfs2(arr[i][j], i, j, 1);
				
				
				for (int u = 0; u < 6; u++)
					for (int m = 0; m < 12; m++)
						if (visited[u][m] >= 4) {
							char word = arr[u][m];
							dfs(word, u, m);
						}
				
			}
		}
	}
	
	for (int i = 0; i < 6; i++)
		for (int j = 0; j< arr[i].size(); j++)
			if (arr[i][j] == '8') {
				jud = true;
				arr[i].erase(arr[i].begin() + j), j--;
			}
	for (int i = 0; i<6; i++)
		if (arr[i].size() < 12) {
			while (arr[i].size() != 12)
				arr[i].push_back('.');
		}

	return jud;
}

int main() {
	for (int i = 0; i < 12; i++) {
		cin >> val[i];
	}
	
	for (int i = 0; i < 6; i++) 
		for (int j = 11; j >= 0; j--)
			arr[i].push_back(val[j][i]);
	
	while (1) {
		bool jud = false;
		
		jud = solve();
		if (jud == false)
			break;
		result++;	

	}
	cout << result << '\n';
}

벡터를 사용하기 위해 입력받은 문자열을 90도 회전해서 벡터에 넣었습니다.

dfs2를 호출해서 탐색하며 visited에 이동값들을 표시했습니다. 

이후 dfs를 통해서 visited값이 4인 값과 연결되는 모든 arr값들을 '8'로 바꿔주었습니다.

그 이후 라운드별로 '8' 값들을 모두 지워주고 뒷부분을 '.' 로 채워주는 방식으로 구현했습니다. 

문제링크: https://www.acmicpc.net/problem/14891

전형적인 시뮬레이션 문제입니다. 시뮬레이션 같은 경우에는 구현과 비슷합니다. 대부분 구현방법을 정의해주는 것의 차이라고 하네요.

각 상태별로 상황을 나누어 함수로 작성하였고, 데큐를 사용해서 각 톱니의 값을 저장했습니다.

직관적이지만 낭비적인 제 답안입니다.

#include <iostream>
#include <string>
#include <deque>
using namespace std;
deque <int> arr[4];
int k = 0, a = 0, b = 0;
int result = 0;


void one_c() {//정

	if (arr[0][2] != arr[1][6]) { // 반대
		if (arr[1][2] != arr[2][6] ) { //정
			if (arr[2][2] != arr[3][6] ) {//반대
				int temp = arr[3].front(); //반대 
				arr[3].pop_front();
				arr[3].push_back(temp);
			}
			int temp = arr[2].back(); //정방향
			arr[2].pop_back();
			arr[2].push_front(temp);
		}
		int temp = arr[1].front(); //반대 
		arr[1].pop_front();
		arr[1].push_back(temp);

	}
	int temp = arr[0].back(); //정방향
	arr[0].pop_back();
	arr[0].push_front(temp);

}
void one_k() {//반

	if (arr[0][2] != arr[1][6]) { // 정
		if (arr[1][2] != arr[2][6]) { // 반
			if (arr[2][2] != arr[3][6]) {//정
				int temp = arr[3].back(); //정 
				arr[3].pop_back();
				arr[3].push_front(temp);
			}
			int temp = arr[2].front(); //반
			arr[2].pop_front();
			arr[2].push_back(temp);
		}
		int temp = arr[1].back(); //정
		arr[1].pop_back();
		arr[1].push_front(temp);

	}
	int temp = arr[0].front(); //반
	arr[0].pop_front();
	arr[0].push_back(temp);
}

void two_c() { //정
	
	if (arr[0][2] != arr[1][6]) { //반
		int temp = arr[0].front(); //반
		arr[0].pop_front();
		arr[0].push_back(temp);
	}
	if (arr[1][2] != arr[2][6]) { //반 
		if (arr[2][2] != arr[3][6]) {//정
			int temp = arr[3].back(); //정 
			arr[3].pop_back();
			arr[3].push_front(temp);

		}
		int temp = arr[2].front(); //반
		arr[2].pop_front();
		arr[2].push_back(temp);
	}

	int temp = arr[1].back(); //정
	arr[1].pop_back();
	arr[1].push_front(temp);

}
void two_k() { //반
	if (arr[0][2] != arr[1][6]) { //정
		int temp = arr[0].back(); //정
		arr[0].pop_back();
		arr[0].push_front(temp);
	}
	if (arr[1][2] != arr[2][6]) { //정 
		if (arr[2][2] != arr[3][6]) {//반
			int temp = arr[3].front(); //반 
			arr[3].pop_front();
			arr[3].push_back(temp);

		}
		int temp = arr[2].back(); //정
		arr[2].pop_back();
		arr[2].push_front(temp);
	}

	int temp = arr[1].front(); //반
	arr[1].pop_front();
	arr[1].push_back(temp);
}
void three_c() { //정
	if (arr[2][2] != arr[3][6]) { //반
		int temp = arr[3].front(); //반 
		arr[3].pop_front();
		arr[3].push_back(temp);
	}
	if (arr[1][2] != arr[2][6]) { //반 
		if (arr[0][2] != arr[1][6]) { //정 
			int temp = arr[0].back(); //정
			arr[0].pop_back();
			arr[0].push_front(temp);
		}
		int temp = arr[1].front(); //반
		arr[1].pop_front();
		arr[1].push_back(temp);
	}

	int temp = arr[2].back(); //정
	arr[2].pop_back();
	arr[2].push_front(temp);
}
void three_k() { //반
	if (arr[2][2] != arr[3][6]) { //정
		int temp = arr[3].back(); //정 
		arr[3].pop_back();
		arr[3].push_front(temp);
	}
	if (arr[1][2] != arr[2][6]) { //정 
		if (arr[0][2] != arr[1][6]) { //반 
			int temp = arr[0].front(); //반
			arr[0].pop_front();
			arr[0].push_back(temp);
		}
		int temp = arr[1].back(); //정
		arr[1].pop_back();
		arr[1].push_front(temp);
	}

	int temp = arr[2].front(); //반
	arr[2].pop_front();
	arr[2].push_back(temp);
}

void four_c() { //정
	if (arr[2][2] != arr[3][6]) { // 반대

		if (arr[1][2] != arr[2][6]) { //정
			if (arr[0][2] != arr[1][6]) {//반대
				int temp = arr[0].front(); //반대 
				arr[0].pop_front();
				arr[0].push_back(temp);
			}
			int temp = arr[1].back(); //정방향
			arr[1].pop_back();
			arr[1].push_front(temp);
		}

		int temp = arr[2].front(); //반대 
		arr[2].pop_front();
		arr[2].push_back(temp);

	}
	int temp = arr[3].back(); //정방향
	arr[3].pop_back();
	arr[3].push_front(temp);

}


void four_k() { //반
	if (arr[2][2] != arr[3][6]) { // 정
		if (arr[1][2] != arr[2][6]) { //반
			if (arr[0][2] != arr[1][6]) {//정
				int temp = arr[0].back(); //정 
				arr[0].pop_back();
				arr[0].push_front(temp);
			}
			int temp = arr[1].front(); //반
			arr[1].pop_front();
			arr[1].push_back(temp);
		}
		int temp = arr[2].back(); //정
		arr[2].pop_back();
		arr[2].push_front(temp);

	}
	int temp = arr[3].front(); //반
	arr[3].pop_front();
	arr[3].push_back(temp);

}


int main() {

	for (int i = 0; i < 4; i++) {
		string num;
		cin >> num;
		for (int j = 0; j < 8; j++)
			arr[i].push_back(num[j]- '0');
	}
	cin >> k;

	while (k--) {
		cin >> a >> b;
		if (a == 1 && b == 1)
			one_c();
		else if (a == 1 && b == -1)
			one_k();
		else if (a == 2 && b == 1)
			two_c();
		else if (a == 2 && b == -1)
			two_k();
		else if (a == 3 && b == 1)
			three_c();
		else if (a == 3 && b == -1)
			three_k();
		else if (a == 4 && b == 1)
			four_c();
		else if (a == 4 && b == -1) 
			four_k();
		
	}
	if (arr[0].front() == 1)
		result += 1;
	if (arr[1].front() == 1)
		result += 2;
	if (arr[2].front() == 1)
		result += 4;	
	if (arr[3].front() == 1)
		result += 8;


	cout << result << endl;
	
}

복붙이 많아서 구현의 큰 어려움없었습니다.

하지만 굳이 8가지의 상황을 나눠서 구현할 필요가 없던 문제입니다.

이렇게 작성하는 것의 단점은 오타를 찾기 힘들다는 것입니다. 코드가 길기때문에 조심하지 않으면 오타나 논리에러를 만들것이고, 테스트케이스를 통과했는데, 해당 에러를 못찾으면 그때부터 지옥의 시작입니다. 

그래서 

• 시뮬레이션에서는 구현전에 최대한 자세하게 청사진을 만든다.
• 구현 중간중간 수시로 테스트케이스를 만들어 대입해보며, 에러가 없는지 수시로 찾는다.

이 두가지를 지키면서 꼼꼼하게 작성해야합니다. 

아래 코드는 다른 분의 좀더 컴팩트한 답안입니다. 

#include <cstdio>
using namespace std;

#define S '1'
#define right(int) (int + 2) % 8
#define left(int) (int - 2 + 8) % 8

char list[4][8];
int N, ans = 0;
int pos[4] = { 0, };

void run(int n, int d, bool bl, bool br) {
	if (n < 0 || n >= 4) return;

	if (n + 1 < 4 && !br) 
		if (list[n][right(pos[n])] != list[n + 1][left(pos[n + 1])]) 
			run(n + 1, d * -1, true, false);
	
	if (n - 1 >= 0 && !bl) 
		if (list[n - 1][right(pos[n - 1])] != list[n][left(pos[n])]) 
			run(n - 1, d * -1, false, true);

	pos[n] = (pos[n] + (d * -1) + 8) % 8;
}

int main() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 8; j++) 
			scanf(" %c", &list[i][j]);
	}

	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int n, d;
		scanf("%d %d", &n, &d);
		run(n - 1, d, false, false);
	}

	for (int i = 0; i < 4; i++)
		if (list[i][pos[i]] == S)
			ans += 1 << i;

	printf("%d\n", ans);

	return 0;
}

톱니바퀴이동읠 8가지유형을 묶어버리고, 재귀함수를 사용함으로써 컴팩트하게 구현했습니다.

밑에는 조금 덜 컴팩트하지만, 직관적인 코드입니다.

#include <iostream>

#include <string>

#include <deque>

#include <queue>

#include <cmath>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

 

        deque<int> dq[5];

        for (int i = 1; i < 5; i++)

        {

                 string s;

                 cin >> s;

 

                 for(int j=0; j<s.length(); j++)

                         dq[i].push_back(s[j] - '0');

        }

 

        int K;

        cin >> K;

        for (int i = 0; i < K; i++)

        {

                 int num, dir;

                 cin >> num >> dir;

 

                 int idx = num;

                 int tempDir = dir;

                 queue<pair<int, int>> q;

                 q.push({ idx, tempDir });

 

                 //check right

                 while (1)

                 {

                         if (idx == 4)

                                 break;

 

                         idx++;

                         tempDir *= -1;

                         if (dq[idx - 1][2] != dq[idx][6])

                                 q.push({ idx, tempDir });

                         else

                                 break;

                 }

 

                 idx = num;

                 tempDir = dir;

                 //check left

                 while (1)

                 {

                         if (idx == 1)

                                 break;

 

                         idx--;

                         tempDir *= -1;

                         if (dq[idx + 1][6] != dq[idx][2])

                                 q.push({ idx, tempDir });

                         else

                                 break;

                 }

 

                 //rotate the magnet

                 while (!q.empty())

                 {

                         int cur = q.front().first;

                         int rotate = q.front().second;

                         q.pop();

 

                         //clockwise

                         if (rotate == 1)

                         {

                                 int temp = dq[cur].back();

                                 dq[cur].pop_back();

                                 dq[cur].push_front(temp);

                         }

                         //anti clockwise

                         else

                         {

                                 int temp = dq[cur].front();

                                 dq[cur].pop_front();

                                 dq[cur].push_back(temp);

                         }

                 }

        }

 

        int result = 0;

        for (int i = 1; i < 5; i++)

                 if (dq[i].front() == 1)

                         result += (int)pow(2, i - 1);

 

        cout << result << "\n";

        return 0;

}

출처: https://jaimemin.tistory.com/1174

코드의 답은 없습니다. 

선택은 여러분의 몫! ㅎㅎ

문제출처:https://www.acmicpc.net/problem/14500

시뮬레이션문제입니다.

차근차근 하나의 도형의 경우를 수를 적용해보셔야 합니다.

반복문 작성시 매번 테스트케이스를 입력해보면서 조기에 오류를 찾아야합니다...

다 작성하고 예외를 찾으려고 하면 절대 못찾아요....

주의하셔야 할 조건은 회전이나 대칭을 시켜도 된다 입니다.

1번 도형같은 경우에는  2가지 모양이 나옵니다.

한가지 좌우로 대칭하고 돌려도 한가지 모양만 나옵니다.

제일 괴랄한 모양으로 돌리고 대칭함으로써 총 8가지의 모양이 나옵니다.

대칭과 회전시 중복하는 모양이 생기기때문에 총 4가지 모양이 나옵니다.

역시 대칭과 회전시 중복하는 모양이 생기기때문에 총 4가지 모양이 나옵니다.

아래는 정답코드입니다.

코드확인해 보시고 꼭 직접 작성해서 풀어보세요 :) 

#include <iostream>
using namespace std;
/*
1번은 회전이 가능한 4가지 경우  -> 아래 오른쪽만 해주면 됨
3번 부터는 회전이나 대칭을 시키는게 가능하기에 각 8가지
*/
int n = 0, m = 0, result = 0;
int arr[501][501] = { 0 };

void num1() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= m - 4; j++)
			if ((arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i][j + 3]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i][j + 3]);

	for (int i = 0; i < m; i++)
		for (int j = 0; j <= n - 4; j++)
			if ((arr[j][i] + arr[j + 1][i] + arr[j + 2][i] + arr[j + 3][i]) > result) result = (arr[j][i] + arr[j + 1][i] + arr[j + 2][i] + arr[j + 3][i]);
}


void num2() {
	for (int i = 0; i < n - 1; i++)
		for (int j = 0; j < m - 1; j++)
			if ((arr[i][j] + arr[i][j + 1] + arr[i + 1][j] + arr[i + 1][j + 1]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i + 1][j] + arr[i + 1][j + 1]);

}

void num3() {
	
	// 기본 모양
	for (int i = 0; i < m - 1; i++)
		for (int j = 0; j <= n - 3; j++)
			if ((arr[j][i] + arr[j + 1][i] + arr[j + 2][i] + arr[j + 2][i + 1]) > result) result = (arr[j][i] + arr[j + 1][i] + arr[j + 2][i] + arr[j + 2][i + 1]);
	// 기본 대칭
	for (int i = 1; i < m; i++)
		for (int j = 0; j <= n - 3; j++)
			if ((arr[j][i] + arr[j + 1][i] + arr[j + 2][i] + arr[j + 2][i - 1]) > result) result = (arr[j][i] + arr[j + 1][i] + arr[j + 2][i] + arr[j + 2][i - 1]);
	//위로 90도
	for (int i = 1; i < n; i++)
		for (int j = 0; j <= m - 3; j++)
			if ((arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i - 1][j + 2]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i - 1][j + 2]);
	//위로 90도 대칭
	for (int i = 0; i < n - 1; i++)
		for (int j = 0; j <= m - 3; j++)
			if ((arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 2]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 2]);
	// 위로 180도
	for (int i = 2; i < n; i++)
		for (int j = 1; j < m; j++)
			if ((arr[i][j] + arr[i - 1][j] + arr[i - 2][j] + arr[i - 2][j - 1]) > result) result = (arr[i][j] + arr[i - 1][j] + arr[i - 2][j] + arr[i - 2][j - 1]);
	// 위로 180도 대칭 
	for (int i = 2; i < n; i++)
		for (int j = 0; j < m - 1; j++)
			if ((arr[i][j] + arr[i - 1][j] + arr[i - 2][j] + arr[i - 2][j + 1]) > result) result = (arr[i][j] + arr[i - 1][j] + arr[i - 2][j] + arr[i - 2][j + 1]);
	// 위로 270도 
	for (int i = 0; i < n - 1; i++)
		for (int j = 0; j < m - 2; j++)
			if ((arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j]);
	// 위로 270도  대칭 
	for (int i = 1; i < n; i++)
		for (int j = 0; j < m - 2; j++)
			if ((arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i - 1][j]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i - 1][j]);
}

void num4() {
	
	// 원래
	for (int i = 0; i < n - 2; i++)
		for (int j = 0; j < m - 1; j++)
			if ((arr[i][j] + arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 2][j + 1]) > result) result = (arr[i][j] + arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 2][j + 1]);
	//원래 대칭 
	for (int i = 0; i < n - 2; i++)
		for (int j = 1; j < m; j++)
			if ((arr[i][j] + arr[i + 1][j] + arr[i + 1][j - 1] + arr[i + 2][j - 1]) > result) result = (arr[i][j] + arr[i + 1][j] + arr[i + 1][j - 1] + arr[i + 2][j - 1]);
	//위로 90도
	for (int i = 1; i < n; i++)
		for (int j = 0; j < m - 2; j++)
			if ((arr[i][j] + arr[i][j + 1] + arr[i - 1][j + 1] + arr[i - 1][j + 2]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i - 1][j + 1] + arr[i - 1][j + 2]);
	//위로 90도 대칭
	for (int i = 0; i < n - 1; i++)
		for (int j = 0; j < m - 2; j++)
			if ((arr[i][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 1][j + 2]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 1][j + 2]);
			
}

void num5() {
	// ㅜ
	for (int i = 0; i < n - 1; i++)
		for (int j = 0; j < m - 2; j++)
			if ((arr[i][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i][j + 2]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i][j + 2]);
	// ㅗ
	for (int i = 1; i < n; i++)
		for (int j = 0; j < m - 2; j++)
			if ((arr[i][j] + arr[i][j + 1] + arr[i - 1][j + 1] + arr[i][j + 2]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i - 1][j + 1] + arr[i][j + 2]);
	// ㅏ
	for (int i = 0; i < n - 2; i++)
		for (int j = 0; j < m - 1; j++)
			if ((arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 1][j + 1]) > result) result = (arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 1][j + 1]);
	// ㅓ
	for (int i = 0; i < n - 2; i++)
		for (int j = 1; j < m; j++)
			if ((arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 1][j - 1]) > result) result = (arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 1][j - 1]);

}

int main() {
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];
	num1();
	num2();
	num3();
	num4();
	num5();
	cout << result << "\n";

}

문제링크:https://www.acmicpc.net/problem/1021

실제 데큐를 사용해서 문제에서의 조건을 실행하며 결과값을 얻는 시뮬레이션 문제였습니다. 

저는 c++의 deque를 사용해서 구현하였습니다. 

숫자를 탐색할때 왼쪽으로 빼는게 빠른지, 오른쪽으로 빼는게 빠른지 

index와 arr.size()를 이용해 위치를 비교하였습니다. 

비교적 쉬운 문제 였습니다. 

정답코드입니다. 

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

deque <int> arr;
int n = 0, m = 0;
int cnt = 0;
int arr_m[51];
int main() {
	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		arr.push_back(i);
	for (int i = 0; i < m; i++)
		cin >> arr_m[i];

	for (int i = 0; i < m; i++) {
		
		int num = arr_m[i];
		int num_index = -1;
		for (int i = 0; i < arr.size(); i++) {
			if (num == arr[i])
				num_index = i;
		}

		// 왼쪽으로 가는게 빠른지 오른쪽으로 가는게 빠른지
		
		//1.왼쪽이 이동하는게 빠를때
		if (num_index <= arr.size() - num_index) {
			for (int i = 0; i < num_index; i++) {
				int val = arr.front();
				arr.push_back(val);
				arr.pop_front();
				cnt++;
			}
			arr.pop_front();
		}
		// 2. 오른쪽으로 이동하는게 빠를때 
		else {
			for (int i = arr.size() - 1; i >= num_index; i--) {
				int val = arr.back();
				arr.push_front(val);
				arr.pop_back();
				cnt++;
			}
			arr.pop_front();
		}
	}
	cout << cnt << '\n';
}

시뮬레이션 문제같은 경우에는 미리 청사진을 자세하게 그려놓고 문제를 풀이하는게 중요합니다.

문제에서 요구하는 조건을 꼼꼼히 확인하고 단계별로 코딩을 하면 쉽게 풀 수 있는 문제였습니다. 

주석하는 습관, 디버깅습관을 기를 수 있는 좋은 문제입니다.

// 동 서 남 북 1 2 3 4
/*
 1. 이동할 수 있는 구간인지 확인하고 불가능하면 continue로 이동하지말구 나가기  O
 2. 좌표변경 후, 이동할 수 있으면 주사위 쉐이킹 O
 3. 바닥이 0이면 바닥에 주사위의 해당수를 넣기 O
 4. 바닥이 0이 아니면 칸에 쓰여 있는 수가 주사위의 바닥면으로 복사되며, 칸에 쓰여 있는 수는 0이 된다. O
 5. 윗면 dice[1]을 출력한다. O
*/
#include <iostream>
using namespace std;

int n, m, x, y, k;
int arr[21][21] = { 0 };
int karr[1000] = { 0 };
int dice[7] = { 0, }; // 인덱스 순서대로 값을 나타내는것  6번째가 항상 아래가 되는 구조인거지 

void verifydice(int direction) {
	int temp = 0;

	if (direction == 1) {
		temp = dice[6];
		dice[6] = dice[3];
		dice[3] = dice[1];
		dice[1] = dice[4];
		dice[4] = temp;
		// 2랑 5는 동일한 구조
	}
	else if (direction == 2) {
		temp = dice[6];
		dice[6] = dice[4];
		dice[4] = dice[1];
		dice[1] = dice[3];
		dice[3] = temp;
		// 2랑 5는 동일한 구조
	}
	else if (direction == 3) {
		temp = dice[6];
		dice[6] = dice[5];
		dice[5] = dice[1];
		dice[1] = dice[2];
		dice[2] = temp;
		// 3랑 4는 동일한 구조
	}
	else if (direction == 4) {
		temp = dice[6];
		dice[6] = dice[2];
		dice[2] = dice[1];
		dice[1] = dice[5];
		dice[5] = temp;
		// 3랑 4는 동일한 구조
	}

}

int main() {

	cin >> n >> m >> x >> y >> k; //입력1  (x,y)

	for (int i = 0; i < n; i++) //입력2
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];

	for (int i = 0; i < k; i++) //입력3
		cin >> karr[i];


	for (int s = 0; s < k; s++) { // k번 만큼 횟수

		if (karr[s] == 1) { // 동쪽으로 이동할때 
			if ((y + 1) >= m)
				continue;
			y++;
			verifydice(1);

		}
		else if (karr[s] == 2) { //서쪽으로 이동할때 
			if ((y - 1) < 0)
				continue;
			y--;
			verifydice(2);

		}
		else if (karr[s] == 4) { //남쪽으로 이동할때 
			if ((x + 1) >= n)
				continue;
			x++;
			verifydice(3);

		}
		else if (karr[s] == 3) { //북쪽으로 이동할때 
			if ((x - 1) < 0)
				continue;
			x--;
			verifydice(4);
		}

		//3,4번의 기능을 구현 
		if (arr[x][y] == 0)
			arr[x][y] = dice[6];
		else {
			dice[6] = arr[x][y];
			arr[x][y] = 0;
		}
		//5번
		cout << dice[1] << endl;
	}


}