굳건하게

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

[ 알고리즘풀이 ]

1. BFS 탐색을 진행한다.

2. Visit 을 체크하는 배열을 dp 배열로 선언한다.

dp[x][y] : (0, 0)에서 (x, y)지점까지 가는데 거쳐야하는 '검은방'의 최소 횟수. 로 정의하면

내가 다음에 갈 지점이 '검은방' 이라면 현재 지점의 값 + 1 보다 크다면 가고,  '흰방' 이라면 현재 지점의 값 보다 크다면 간다.

#include<iostream>
#include<queue>

using namespace std;

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

	int n, dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 }, dp[50][50] = {};
	char map[50][51] = {};

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> map[i];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			dp[i][j] = 99999999;

	queue<pair<int, int>> q;
	q.push(make_pair(0, 0));
	dp[0][0] = 0;

	while (!q.empty()) {
		pair<int, int> s = q.front();
		q.pop();

		int curX = s.first, curY = s.second;
		for (int i = 0; i < 4; i++) {
			int nextX = curX + dx[i], nextY = curY + dy[i];
			if (0 <= nextX && nextX < n && 0 <= nextY && nextY < n) {
				if (dp[curX][curY] + 1 < dp[nextX][nextY] && map[nextX][nextY] == '0') {
					dp[nextX][nextY] = dp[curX][curY] + 1;
					q.push(make_pair(nextX, nextY));
				}
				else if(dp[curX][curY] < dp[nextX][nextY] && map[nextX][nextY] == '1'){
					dp[nextX][nextY] = dp[curX][curY];
					q.push(make_pair(nextX, nextY));
				}
			}
		}
	}
	cout << dp[n - 1][n - 1];
	return 0;
}

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

[ 알고리즘풀이 ]

나누는 수 1,000,000,007 이 소수이므로 페르마 소정리와 고속 지수화 연산을 이용하면 된다.

( 고속 거듭제곱 연산 : https://travelbeeee.tistory.com/117?category=800452 )

#include<iostream>
#define P 1000000007

using namespace std;

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

	long long N, K, A = 1, B = 1, C = 1;
	cin >> N >> K;
	for (int i = 1; i <= N; i++)
		A = (A * i) % P;
	for (int i = 1; i <= N - K; i++)
		B = (B * i) % P;
	for (int i = 1; i <= K; i++)
		C = (C * i) % P;
	
	long long ex = P - 2, mulB = B,mulC = C, ansB = 1, ansC = 1;
	while (ex) {
		if (ex % 2 == 1)
			ansB = (ansB * mulB) % P;
		mulB = (mulB * mulB) % P;
		ex /= 2;
	}

	ex = P - 2;
	while (ex) {
		if (ex % 2 == 1)
			ansC = (ansC * mulC) % P;
		mulC = (mulC * mulC) % P;
		ex /= 2;
	}

	cout << (((A * ansB) % P)* ansC) % P;
}

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

[ 알고리즘풀이 ]

curMap[x][y] : 현재 (x, y) 지점의 양분

dead[x][y] : (x, y) 지점에 봄에 죽은 나무들의 양분

A[x][y] : (x, y) 지점에 겨울에 추가될 양분

tree[x][y] : (x, y) 지점에 존재하는 나무들의 나이 ( 더 좋은 자료구조가 생각이 안나서, 각 지점마다 vector 배열을 만들어 현재 그 지점에 존재하는 나무들의 나이를 저장했습니다. )

1. Spring

각 지점마다 나무가 존재한다면, 나무들의 나이를 sort해서 어린 나무부터 양분을 줍니다. 이때, 양분이 부족한 나무들을 count 해주고, 나이 순으로 sort가 된 상태고, 어린 나무부터 양분을 주므로 count 만큼 pop_back 을 진행하면 죽은 나무들을 vector 에서 제외할 수 있습니다. 또, 나무가 죽었다면 dead 에 나이 / 2 만큼 양분을 추가해줍니다.

2. Summer

각 지점마다 curMap[x][y] += dead[x][y] 를 진행하고, dead[x][y] = 0 (초기화) 를 진행합니다.

3. Fall

각 지점마다 나무가 존재한다면, 나무들의 나이를 순회하며 나이가 5의 배수인 나무가 있다면 주변에 나무를 추가해줍니다.

4. Winter

각 지점마다 curMap[x][y] += A[x][y] 를 진행해줍니다.

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int N, M, K, curMap[11][11] = {}, dead[11][11] = {}, A[11][11] = {}, x, y, z;
int dx[8] = { -1, -1, -1, 0, 0, 1, 1, 1 }, dy[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
vector<int> tree[11][11] = {};

void spring(void) {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (tree[i][j].empty())
				continue;

			int deadTree = 0;
			sort(tree[i][j].begin(), tree[i][j].end());
			for (int k = 0; k < tree[i][j].size(); k++) {
				if (tree[i][j][k] <= curMap[i][j]) {
					curMap[i][j] -= tree[i][j][k];
					tree[i][j][k] += 1;
				}
				else {
					dead[i][j] += tree[i][j][k] / 2;
					deadTree++;
				}
			}
			for (int k = 0; k < deadTree; k++)
				tree[i][j].pop_back();
		}
	}
}

void summer(void) {
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++){
			curMap[i][j] += dead[i][j];
			dead[i][j] = 0;
		}
}

void fall(void) {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (tree[i][j].empty())
				continue;
			for (int k = 0; k < tree[i][j].size(); k++) {
				if (tree[i][j][k] % 5 == 0) {
					for (int l = 0; l < 8; l++) {
						int x = i + dx[l], y = j + dy[l];
						if (1 <= x && x <= N && 1 <= y && y <= N)
							tree[x][y].push_back(1);
					}
				}
			}
		}
	}
}

void winter(void) {
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			curMap[i][j] += A[i][j];
}

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

	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++){
			cin >> A[i][j];
			curMap[i][j] = 5;
		}

	for (int i = 1; i <= M; i++) {
		cin >> x >> y >> z;
		tree[x][y].push_back(z);
	}
		
	while (K--){
		spring();
		summer();
		fall();
		winter();
	}

	int ans = 0;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			ans += tree[i][j].size();
	cout << ans;
}

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

[ 알고리즘풀이 ]

 CCTV는 최대 8개가 존재하고, 모든 종류의 CCTV가 가질 수 있는 경우의 수가 최대 4가지 이므로, 백트래킹을 이용해 모든 경우의 수에 대해서 조사를 해도 시간 초과 문제에 걸리지 않는다.

1. 백트래킹을 이용해 CCTV 마다 상태를 정해준다.

2. CCTV마다 상태가 정해졌다면, map을 tempMap에 복사한다. 그 후, CCTV의 종류와 상태에 따라서 CCTV가 감시하고 있는 방향들을 tempMap에서 check 해준다.

3. tempMap에 check해주는 과정이 마무리되면, 사각지대를 count 해 답을 갱신한다.

4. 2 ~ 3 과정을 반복한다.

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int N, M, C = 0, map[8][8], ans = 987654321;
vector<pair<pair<int, int>,int>> v;
vector<int> dir;

int getArea(int tempMap[8][8]) {
	int count = 0;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (tempMap[i][j] == 0)
				count++;
	return count;
}

void up(int x, int y, int tempMap[8][8]) {
	for (int i = x - 1; i >= 0; i--) {
		if (tempMap[i][y] == 0)
			tempMap[i][y] = 9;
		else if (tempMap[i][y] == 6)
			break;
	}
	return;
}

void right(int x, int y, int tempMap[8][8]) {
	for (int j = y + 1; j < M; j++) {
		if (tempMap[x][j] == 0)
			tempMap[x][j] = 9;
		else if (tempMap[x][j] == 6)
			break;
	}
	return;
}

void left(int x, int y, int tempMap[8][8]) {
	for (int j = y - 1; j >= 0; j--) {
		if (tempMap[x][j] == 0)
			tempMap[x][j] = 9;
		else if (tempMap[x][j] == 6)
			break;
	}
	return;
}

void down(int x, int y, int tempMap[8][8]) {
	for (int i = x + 1; i < N; i++){
		if (tempMap[i][y] == 0)
			tempMap[i][y] = 9;
		else if (tempMap[i][y] == 6)
			break;
	}
	return;
}

void setWatched(void) {
	// Map 복제.
	int tempMap[8][8] = {};
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			tempMap[i][j] = map[i][j];
	// CCTV 종류와 방향에 따라서 셋팅해보자.
	for (int i = 0; i < C; i++) {
		if (v[i].second == 1) { // 1번 CCTV
			if (dir[i] == 1)
				up(v[i].first.first, v[i].first.second, tempMap);
			else if (dir[i] == 2)
				right(v[i].first.first, v[i].first.second, tempMap);
			else if (dir[i] == 3)
				down(v[i].first.first, v[i].first.second, tempMap);
			else
				left(v[i].first.first, v[i].first.second, tempMap);
		}
		else if (v[i].second == 2) { // 2번 CCTV
			if (dir[i] % 2 == 1) {
				right(v[i].first.first, v[i].first.second, tempMap);
				left(v[i].first.first, v[i].first.second, tempMap);
			}
			else {
				up(v[i].first.first, v[i].first.second, tempMap);
				down(v[i].first.first, v[i].first.second, tempMap);
			}
		}
		else if (v[i].second == 3) { // 3번 CCTV
			if (dir[i] == 1){
				up(v[i].first.first, v[i].first.second, tempMap);
				right(v[i].first.first, v[i].first.second, tempMap);
			}
			else if (dir[i] == 2){
				right(v[i].first.first, v[i].first.second, tempMap);
				down(v[i].first.first, v[i].first.second, tempMap);
			}
			else if (dir[i] == 3){
				down(v[i].first.first, v[i].first.second, tempMap);
				left(v[i].first.first, v[i].first.second, tempMap);
			}
			else{
				left(v[i].first.first, v[i].first.second, tempMap);
				up(v[i].first.first, v[i].first.second, tempMap);
			}
		}
		else if (v[i].second == 4) { // 4번 CCTV
			if (dir[i] == 1) {
				up(v[i].first.first, v[i].first.second, tempMap);
				right(v[i].first.first, v[i].first.second, tempMap); 
				left(v[i].first.first, v[i].first.second, tempMap);
			}
			else if (dir[i] == 2) {
				up(v[i].first.first, v[i].first.second, tempMap);
				right(v[i].first.first, v[i].first.second, tempMap);
				down(v[i].first.first, v[i].first.second, tempMap);
			}
			else if (dir[i] == 3) {
				right(v[i].first.first, v[i].first.second, tempMap);
				down(v[i].first.first, v[i].first.second, tempMap);
				left(v[i].first.first, v[i].first.second, tempMap);
			}
			else {
				down(v[i].first.first, v[i].first.second, tempMap);
				left(v[i].first.first, v[i].first.second, tempMap);
				up(v[i].first.first, v[i].first.second, tempMap);
			}
		}
		else {
			up(v[i].first.first, v[i].first.second, tempMap);
			right(v[i].first.first, v[i].first.second, tempMap);
			down(v[i].first.first, v[i].first.second, tempMap);
			left(v[i].first.first, v[i].first.second, tempMap);
		}
	}
	ans = min(ans, getArea(tempMap));
	return;
}

void BT(int c) {
	if (c == C) {
		setWatched();
		return;
	}
	for (int i = 1; i <= 4; i++) {
		dir.push_back(i);
		BT(c + 1);
		dir.pop_back();
	}
}

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

	cin >> N >> M;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++){
			cin >> map[i][j];
			if (1 <= map[i][j] && map[i][j] <= 5) {
				v.push_back(make_pair(make_pair(i, j), map[i][j]));
				C++;
			}
		}
	BT(0);
	cout << ans << '\n';
}