굳건하게

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

시뮬레이션 BFS

 Puyo Puyo 게임을 구현하는 문제로 시뮬레이션입니다.

1)

 현재 Map 상태에서 BFS 탐색을 통해 4개 이상 상하좌우로 연결되어있는 블록들을 모두 체크한다. 이때, Map의 모든 지점에서 블록이 있다면 BFS 탐색을 진행하고, BFS 탐색을 진행하는 동안 이동하는 경로를 다 저장한다. 경로가 4개 이상이면(4개 이상 연결된 블록이 있다면) 해당 블록들을 따로 체크해둔다.

2)

 1)에서 4개 이상 연결된 블록이 없었다면 게임을 끝낸다.

3)

현재 Map 상태에서 블록들을 아래로 이동시켜준다.

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
	char map[12][7] = {};
	for (int i = 0; i < 12; i++)
		cin >> map[i];
	
	int cnt = 0;
	while (1) {
		// 터뜨릴 수 있는 모든 뿌요를 터뜨리자.
		bool isFinished = false;
		bool isBomb[12][6] = {};
		for (int i = 11; i >= 0; i--) {
			for (int j = 0; j < 6; j++) {
				if (map[i][j] != '.' && isBomb[i][j] == false) {
					// 스팟마다 BFS 탐색을 진행하면서 경로 저장.
					queue<pair<int, int>> q;
					vector<pair<int, int>> temp;
					q.push({ i, j });
					isBomb[i][j] = true;
					temp.push_back({ i, j });
					while (!q.empty()) {
						int curX = q.front().first, curY = q.front().second;
						q.pop();
						for (int k = 0; k < 4; k++) {
							int nX = curX + dx[k], nY = curY + dy[k];
							if (!(0 <= nX && nX < 12 && 0 <= nY && nY < 6)) continue;
							if (map[nX][nY] != map[curX][curY]) continue;
							if (isBomb[nX][nY]) continue;
							q.push({ nX, nY });
							temp.push_back({ nX, nY });
							isBomb[nX][nY] = true;
						}
					}
					if (temp.size() >= 4) {
						isFinished = true;
					}
					else { // 지금 탐색한 경로는 4개 이상의 블록 X
						for (int k = 0; k < temp.size(); k++) {
							isBomb[temp[k].first][temp[k].second] = false;
						}
					}
				}
			}
		}
		// 터뜨릴 수 있는 뿌요가 없다면 break;
		if (!isFinished) break;
		// 먼저 터진 부분 처리!
		for (int i = 0; i < 12; i++)
			for (int j = 0; j < 6; j++)
				if (isBomb[i][j]) map[i][j] = '.'; 
		// 맵을 이동하자.
		for (int j = 0; j < 6; j++) {
			for (int k = 0; k < 11; k++) { // 각 열마다 12번씩 행을 아래로 끌어내리자.
				for (int i = 10; i >= 0; i--) {
					if (map[i][j] != '.') {
                    	int l = i + 1;
						if (map[l][j] != '.') continue;
						while (l < 12 && map[l][j] == '.')
							l++;
						map[l - 1][j] = map[i][j];
						map[i][j] = '.';
					}
				}
			}
		}
		cnt++;
	}
	cout << cnt << '\n';
	return 0;
}

문제 : https://www.acmicpc.net/problem/1038

백트레킹 경우의수 수학

 문제에서 정의한 감소하는 수는 같은 110 같이 같은 값도 가지면 안되므로, 최대 9876543210 입니다. 

 다르게 생각하면 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } 에서 숫자들을 뽑아서 만들 수 있는 모든 조합 2^10 에서 하나도 안뽑는 경우와 '0'만 뽑는 경우를 제외한 1022가지 경우가 감소하는 수의 전체 경우의 수라는 것을 알 수 있습니다. 

 --> 백트레킹을 이용해 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } 에서 숫자를 뽑는 모든 경우에 대해서 String 으로 변환한 후 저장하고 sort 한 다음 N번 째 감소하는 수를 출력한다. 이때, N이 1023보다 크거나 같다면 감소하는 수가 존재하지 않으므로 -1을 출력한다.

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

int N;
vector<string> ans;

bool cmp(string A, string B) {
	if (A.length() == B.length()) {
		for (int i = 0; i < A.length(); i++){
			if (A[i] == B[i]) continue;
			return A[i] < B[i];
		}
	}
	return (A.length() < B.length());

}
void backtracking(bool check[10], int start) {
	string s = "";
	for (int i = 9; i >= 0; i--)
		if (check[i])
			s += ('0' + i);
	ans.push_back(s);

	for (int i = start; i < 10; i++) {
		if (check[i] == false) {
			check[i] = true;
			backtracking(check, i + 1);
			check[i] = false;
		}
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	if (N > 1022) cout << -1;
	else {
		bool check[10] = {};
		backtracking(check, 0);
		sort(ans.begin(), ans.end(), cmp);
		cout << ans[N + 1] << '\n';
	}
	return 0;
}

문제 : https://www.acmicpc.net/problem/11585

문자열 KMP

 우리는 주어지는 입력 A, B에서 B를 원형으로 회전시켜가며 A가 있는지 없는지 탐색할 수 있어야된다.

따라서, 문자열 검색인 KMP 알고리즘을 생각해야되고 B를 원형으로 회전시켜가며 생각하는 부분은 B 에다가 B를 한 번 더 붙여주면 쉽게 해결이 된다.

예시) 

I W A N T M E A T 

E A T I W A N T M 를

E A T I W A N T M E A T I W A N T M 에서 I W A N T M E A T 을 찾는 문제로 바꿔서 바라보면 쉽게 해결할 수 있다.

#include<iostream>
#include<vector>

using namespace std;

int N;
char input1[1000001], input2[2000001];

vector<int> getPartialMatch() {
	vector<int> pi(N, 0);
	int begin = 1, matched = 0;
	while (begin + matched < N) {
		if (input1[begin + matched] == input1[matched]) {
			matched++;
			pi[begin + matched - 1] = matched;
		}
		else {
			if (matched == 0) begin++;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
	return pi;
}

int KMP() {
	int cnt = 0;
	vector<int> pi = getPartialMatch();
	int begin = 0, matched = 0;
	while (begin < N) {
		if (matched < N && input2[begin + matched] == input1[matched]) {
			matched++;
			if (matched == N) cnt++;
		}
		else {
			if (matched == 0) begin++;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
	return cnt;
}
int gcd(int A, int B) {
	while (B) {
		int r = A % B;
		A = B;
		B = r;
	}
	return A;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> input1[i];
	for (int i = 0; i < N; i++)
		cin >> input2[i];
	for (int i = N; i < 2 * N; i++)
		input2[i] = input2[i - N];
	int cnt = KMP();
	int r = gcd(N, cnt);
	cout << cnt / r << '/' << N / r << '\n';
	return 0;
}

문제 : https://www.acmicpc.net/problem/2671

문자열 문자열처리

(100~1~|01)~ 를 만족하는지 아닌지 판단하면 된다.

● (100~1~|01)~ 는 100~1~ 과 01의 조합으로 이루어져있다. 따라서, 0으로 시작하면 "01" 이고, 1로 시작하면 "100~1~" 임을 알 수 있다.

● 0으로 시작하면 "01" 을 제외하고 다 NOISE인 경우이다.  따라서, 0을 만나면 다음 칸이 1인지 체크하고 맞다면 2칸 앞으로 건너뛰면 된다.

● 1로 시작하면 100~1~ 이다. 이때, 100 / 1 은 무조건 존재해야한다. 먼저, 1을 만나면 뒤에 0이 2개 있는지 체크하고, 1000000 과 같지 100~ 에 해당되는 0들을 다 건너뛴다. 그 후, 111111과 같이 1~에 해당되는 부분들을 다 건너 뛴다. 이때, 체크해줘야하는 부분이 있다. 100~ 에 해당되는 부분이 다 끝나고, 1~ 로 해당되는 부분은 11111111과 같이 1이 여러 번 반복되도 된다. 하지만, 10011001 과 같이 1001 / 1001 로 나눠지는 경우에는 10011 까지 1을 반복해서 앞에 부분으로 종속시키면 안되므로, 현재 '1' 인데 뒤에 "00" 이 붙은 경우는 다시 위에부터 순회를 진행해주면 된다.

반례

1001001 : NOISE

1000001110000001 : SUBMARINE

#include<iostream>
#include<string>

using namespace std;

bool checkAns(string N) {
	int i = 0, s = N.length();
	while (i < s) {
		if (N[i] == '0') {
			if (i + 1 >= s) return false;
			if (N[i + 1] != '1') return false;
			i += 2;
		}
		else { // 시작이 1이면 최소 1 00 1
			if (i + 3 >= s) return false;
			if (!(N[i + 1] == '0' && N[i + 2] == '0')) return false; // 일단 무조건 뒤에 0이 2개 나와야됨.
			i++;
			while (i < s && N[i] == '0')
				i++;
			if (i >= s) return false; // 1 뒤에붙은 0들을 다 추적했더니 끝나버린 경우.
			i++;
			while (i < s && N[i] == '1') {
				if (i + 2 < s && N[i + 1] == '0' && N[i + 2] == '0') break;
				i++;
			}
		}
	}
	return true;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	string s;
	cin >> s;
	if (checkAns(s)) cout << "SUBMARINE";
	else cout << "NOISE";
	return 0;
}