이것 저것 &

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

5427번 불의 이전단계 문제입니다.

알고리즘은

• 1. 불먼저 전파
• 2. 사람 이동
• 1, 2번을 사람이 이동가능한 칸이 있을 때 까지 반복
• 3. 결과 값 도출

순입니다.

#include <iostream>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
int h = 0, w = 0;
int visited[1000][1000] = { 0 };
char arr[1000][1000];

queue <int> fire[2];
queue <int> people[2];

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

void bfs() {
	//초기값 입력
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			if (arr[i][j] == 'F')
				fire[0].push(i), fire[1].push(j);
			else if (arr[i][j] == 'J')
				people[0].push(i), people[1].push(j), visited[i][j] = 1;



	while (!people[0].empty()) { //상근이가 이동할 경로가 없을 때 까지 반복
								 //1. 불먼저 전파
		int fire_cnt = fire[0].size();
		while (fire_cnt--) {
			int yy = fire[0].front();
			int xx = fire[1].front();
			fire[0].pop(), fire[1].pop();
			for (int i = 0; i < 4; i++) {
				int y = yy + y_ar[i];
				int x = xx + x_ar[i];
				if (y >= 0 && y < h && x >= 0 && x < w)
					if (arr[y][x] == '.' || arr[y][x] == 'J') {
						arr[y][x] = 'F';
						fire[0].push(y), fire[1].push(x);
					}
			}
		}
		//2. 상근좌 이동
		int people_cnt = people[0].size();
		while (people_cnt--) {
			int yy = people[0].front();
			int xx = people[1].front();
			people[0].pop(), people[1].pop();
			for (int i = 0; i < 4; i++) {
				int y = yy + y_ar[i];
				int x = xx + x_ar[i];
				if (y >= 0 && y < h && x >= 0 && x < w)
					if (arr[y][x] == '.' && visited[y][x] == 0) {
						visited[y][x] = visited[yy][xx] + 1;
						people[0].push(y), people[1].push(x);
					}
			}
		}
	}
	//3. 모서리의 visited값들을 확인하고 결과값을 도출
	int result = 1000000;
	bool alive = false;
	for (int i = 0; i < h; i++) {
		if (visited[i][0] != 0) {
			alive = true;
			if (visited[i][0] < result)
				result = visited[i][0];
		}
		if (visited[i][w - 1] != 0) {
			alive = true;
			if (visited[i][w - 1] < result)
				result = visited[i][w - 1];
		}
	}
	for (int j = 0; j < w; j++) {
		if (visited[0][j] != 0) {
			alive = true;
			if (visited[0][j] < result)
				result = visited[0][j];
		}
		if (visited[h - 1][j] != 0) {
			alive = true;
			if (visited[h - 1][j] < result)
				result = visited[h - 1][j];
		}
	}

	if (alive)
		cout << result << '\n';
	else
		cout << "IMPOSSIBLE" << '\n';
}

int main() {

	cin >> h >> w;
	for (int i = 0; i < h; i++) {
		string val;
		cin >> val;
		for (int j = 0; j < val.size(); j++)
			arr[i][j] = val[j];
	}
	bfs();

}

비슷한 유형문제를 풀어보셨다면 어렵지 않습니다.

꼭 이 문제 직접구현해보시고 bfs에 익숙해지세요! 화이팅

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

 bfs문제입니다.

불과 상근이가 함께 이동하기 때문에 각각 bfs를 사용해서 구현하시면 되는 문제입니다.

문제조건에서 

상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

이라고 하기 때문에 불을 먼저 움직여주면 됩니다.

알고리즘은

• 1. 불먼저 전파
• 2. 상근좌 이동
• 1, 2번을 상근좌가 이동가능한 칸이 있을 때 까지 반복
• 3. 결과 값 도출

순입니다.

정답코드입니다.

#include <iostream>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
int t = 0, h = 0, w = 0;
int visited[1000][1000] = { 0 };
char arr[1000][1000];

queue <int> fire[2];
queue <int> people[2];

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

void bfs() {
	//초기값 입력
	for (int i = 0; i < h; i++)  
		for (int j = 0; j < w; j++)
			if (arr[i][j] == '*')
				fire[0].push(i), fire[1].push(j);
			else if(arr[i][j] == '@')
				people[0].push(i), people[1].push(j), visited[i][j] = 1;

	

	while (!people[0].empty()) { //상근이가 이동할 경로가 없을 때 까지 반복
		//1. 불먼저 전파
		int fire_cnt = fire[0].size();
		while (fire_cnt--) {
			int yy = fire[0].front();
			int xx = fire[1].front();
			fire[0].pop(), fire[1].pop();
			for (int i = 0; i < 4; i++) {
				int y = yy + y_ar[i];
				int x = xx + x_ar[i];
				if (y >= 0 && y < h && x >= 0 && x < w) 
					if (arr[y][x] == '.' || arr[y][x] == '@') {
						arr[y][x] = '*';
						fire[0].push(y), fire[1].push(x);
					}
			}
		}
		//2. 상근좌 이동
		int people_cnt = people[0].size();
		while (people_cnt--) {
			int yy = people[0].front();
			int xx = people[1].front();
			people[0].pop(), people[1].pop();
			for (int i = 0; i < 4; i++) {
				int y = yy + y_ar[i];
				int x = xx + x_ar[i];
				if (y >= 0 && y < h && x >= 0 && x < w)
					if (arr[y][x] == '.' && visited[y][x] == 0) {
						visited[y][x] = visited[yy][xx] + 1;
						people[0].push(y), people[1].push(x);
					}
			}
		}
	}
	//3. 모서리의 visited값들을 확인하고 결과값을 도출
	int result = 1000000;
	bool alive = false;
	for (int i = 0; i < h; i++) {
		if (visited[i][0] != 0) {
			alive = true;
			if (visited[i][0] < result)
				result = visited[i][0];
		}
		if (visited[i][w - 1] != 0) {
			alive = true;
			if (visited[i][w - 1] < result)
				result = visited[i][w - 1];
		}
	}
	for (int j = 0; j < w; j++) {
		if (visited[0][j] != 0) {
			alive = true;
			if (visited[0][j] < result)
				result = visited[0][j];
		}
		if (visited[h - 1][j] != 0) {
			alive = true;
			if (visited[h - 1][j] < result)
				result = visited[h - 1][j];
		}
	}

	if (alive)
		cout << result << '\n';
	else
		cout << "IMPOSSIBLE" << '\n';
}

int main() {
	cin >> t;

	while (t--) {
		memset(visited, 0, sizeof(visited));
		while (!fire[0].empty())
			fire[0].pop(), fire[1].pop();

		cin >> w >> h;
		for (int i = 0; i < h; i++) {
			string val;
			cin >> val;
			for (int j = 0; j < val.size(); j++)
				arr[i][j] = val[j];
		}
		bfs();
	}
}

비슷한 유형문제를 풀어보셨다면 어렵지 않습니다.

꼭 이 문제 직접구현해보시고 bfs에 익숙해지세요! 화이팅

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

브루트 포스문제이고 dfs를 통해서 구현해야하는 문제였습니다.

기본적인 구현은 dfs를 통한 재귀로 구현해주시면 됩니다.

문제는 시간초과문제입니다.

확인해야하는 알파벳은 26-5 =21개입니다. 

이때 매번 15-8 =7개 * 50개 의 알파벳을 확인해주는 재귀이기 때문에 가지치기를 잘해야하는 문제였습니다.

가지치기

•  1. k <5, k==26의 극단값 처리 (엄연하게 백트래킹 가지치기는 아니죠)
•  2. dfs에 alpha 변수를 통해서 알파벳 중에서 k-5개를 선택할 때 중복이 안 생기도록 만들기 (이게 백트래킹의 핵심입니다.)
•  3. set 컨테이너를 통해서 arr안에 들어가는 알파벳의 중복을 제거했습니다. (안해도 통과는 됩니다.)

정답 코드입니다. 

#include <algorithm>
#include <iostream>
#include <string>
#include <set>
using namespace std;
bool visited[26] = { 0 };
set<char> arr[51];
int n = 0, k = 0, result = 0;

void dfs(int alpha, int cnt) {
	if (cnt == (k - 5)) {
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			bool jud = true;

			for (auto it = arr[i].begin(); it != arr[i].end(); it++) {
				if (visited[*it - 'a'] == 0) {
					jud = false;
					break;
				}
			}
			
			if (jud == true)
				cnt++;
		}
		 result = max(result,cnt);

		return;
	}

	for (int i = alpha; i < 26; i++) {

		if (visited[i] == 0) {
			visited[i] = 1;
			dfs(i,cnt + 1);
			visited[i] = 0; 
		}
	}

}

int main() {

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

	cin >> n >> k;
	visited['a' - 'a'] = 1;
	visited['c' - 'a'] = 1;
	visited['i' - 'a'] = 1;
	visited['t' - 'a'] = 1;
	visited['n' - 'a'] = 1;

	for (int i = 0; i < n; i++) {
		string v;
		cin >> v;
		for (int j = 0; j < v.size(); j++) {
			if (v[j] != 'a' && v[j] != 'c' && v[j] != 'i' && v[j] != 't' && v[j] != 'n') {
				arr[i].insert(v[j]);
			}
		}
			
	}
	

	if (k < 5) {
		cout << 0 << '\n';
		return 0;
	}
	else if (k == 26) {
		cout << n << '\n';
		return 0;
	}
	dfs(0,0);

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

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

그리디 문제입니다.

항상 최선의 선택을 할 때 결과값이 도출되기 때문입니다.

해당 문제는 n 배열과 m 배열을 내림차순으로 정렬하고 순서대로 큰 짐을 먼저 옮겨주면 되는 문제였습니다.

못 옮기는 기준은 가장 센 크레인 (arr_n[0])이 가장 무거운 짐(arr_m[0]) 보다 작을 때 입니다.

그리고 일반 배열에 O(n*m)로 구현하시면 시간초과입니다. 

최악의 상황에 O(m*n*m) 이 되어 500,000,000로 5초가 걸리기 때문입니다.

정답코드입니다.

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

int arr_n[51] = { 0 };
vector <int> arr_m;
int n = 0, m = 0, result = 0;

bool cmp(int a, int b) {
	if (a > b)return true;
	return false;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr_n[i];
	cin >> m;
	int num = 0;
	for (int i = 0; i < m; i++) {
		cin >> num;
		arr_m.push_back(num);
	}

	sort(arr_n, arr_n + n, cmp);
	sort(arr_m.begin(), arr_m.end(), cmp);

	if (arr_n[0] < arr_m[0]) {
		cout << -1 << endl;
		return 0;
	}

	
	while (1) {
		result++;

		for (int i = 0; i < n; i++) {
			
			for (int j = 0; j < arr_m.size(); j++) {
				if (arr_n[i] >= arr_m[j]) {
					arr_m.erase(arr_m.begin() + j);
					break;
				}
			}
		}
	
		if (arr_m.size() == 0)
			break;
		
	}
	cout << result << '\n';

}

저는 벡터를 사용해서 짐을 뺄때마다 erase로 값을 지워주도록 구현하였습니다.

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

소시지를 하나로 이어붙인 상태 즉, n = 1일때 m - 1번 잘라야 모두에게 같은 크기의 소시지를 줄 수 있다.

즉, 최악의 경우 m - 1 최소의 경우 0번이다. 

그렇다면 소시지가 여러개가 있을 때 어떻게 해야할까?

최대공약수를 생각해보면 답이 나온다. 

소시지를 일자로 두고 일정한 크기 만큼 자를 때 두 수의 (최대 공약수 - 1)  만큼 이미 잘려있을 것이다. 

즉 식은 b - gcd(a,b) 이다. 

#include <iostream>
using namespace std;

int n = 0, m = 0;
int GCD(int a, int b) {
	if (a%b == 0)
		return b;

	return GCD(b, a%b);
}

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

	cout << m - GCD(n, m) << endl;
}

최대 공약수를 구하는 재귀는 위와 같이 구현할 수 있다. 

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

dp문제입니다.

위와 같을때 값을 2*2 =4입니다. 각 점마다 자신의 넓이는 이전 점들의 값과 연관이 있습니다.

점화식은 arr[i][j] 가 1인점에 한해서 dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1], dp[i][j] ) + 1 입니다. 

이전 값들의 크기에 따라서 값이 변하게 되는 구조입니다.

저는 초기값 설정을 어설프게 해서 한번 틀렸었습니다.

1행과 1열 모두 초기값 설정을 해야합니다.

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

int dp[1001][1001] = { 0 };
int result = 0, n = 0, m = 0;
string arr[1001];

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

	for (int i = 0; i < n; i++) {
		dp[i][0] = arr[i][0] - '0';
		result = max(result, dp[i][0]);
	}
	for (int i = 0; i < m; i++) {
		dp[0][i] = arr[0][i] - '0';
		result = max(result, dp[0][i]);
	}

	for (int i = 1; i < n; i++) 
		for (int j = 1; j < m; j++) {
			if (arr[i][j] == '1') {
				dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]);
				dp[i][j] = min(dp[i][j - 1], dp[i][j]);
				dp[i][j]++;
			}
			if (result < dp[i][j])
				result = dp[i][j];
		}
	cout << result*result << '\n';
}

구현자체에 어려움은 없으실 것입니다. 

문제링크: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

코드의 답은 없습니다. 

선택은 여러분의 몫! ㅎㅎ