굳건하게

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

#구현 #시뮬레이션

[ 문제해석 ]

5 x 5 가마에 4 x 4 크기의 재료들을 넣어서 폭탄을 제조한다. 이때, 4 x 4 크기의 재료는 가마의 격자를 벗어날 수 없고, 회전해서 넣을 수 있고 서로 다른 재료를 3가지 가마에 넣는다.

[ 알고리즘핵심 ]

4 x 4 크기의 재료는 최대 10개이고 회전해서 넣을 수 있으므로 최대 40개(회전시킨재료포함)의 재료에서 3가지 재료를 뽑는다고 생각해도 된다. 그 후, 이 재료들을 5 x 5 가마에 넣어야되는데 이때도 가마의 (0, 0) / (0, 1) / (1, 0) / (1, 1) 에 재료를 넣는 경우를 제외하고는 가마를 다 벗어난다.

 따라서, 백트레킹을 이용해 40개에서 3개를 뽑고, 4가지 위치 중에 하나를 고르는 모든 경우의 수를 구해도 복잡도가 40C3 * 4^3 밖에 나오지 않는다. 즉, 1초 안에 가능한 연산이다.

[ 알고리즘풀이 ]

1. 입력을 받으면 시계방향으로 90도, 180도, 270도 회전한 상태도 같이 effect, color 배열에 저장해준다.

2. 백트레킹1 - 백트레킹을 이용해 재료 3개를 뽑는다. 

3. 백트레킹2 - 재료 3개를 다 뽑은 상태에서, 재료 3개의 넣는 위치를 구한다.

4. 플레이게임 - 'W'로 초기화된 가마를 만든 후, 3가지 재료를 정해진 위치에 넣고 red, blue, green, yellow 효능 값을 구해주면 된다.

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

BFS DP

문제 해석

 (1,1) 에서 (r,c) 로 최대한 빠르게 이동하고 싶다. 이때, 일반상태에서는 상하좌우로 한 칸 씩만 이동이 가능하고, t 턴을 소모해 변신상태가 되면 상하좌우 중 '#' 이 있는 워프 지역으로 한 번에 이동이 가능하다.

문제 핵심

 일반 상태로도 진행할 수 있고, 변신 상태로도 탐색을 진행할 수 있으므로 현재 지점에서 일반 이동 과 변신을 시킨 후 변신 이동을 모두 진행해야한다.

알고리즘

 Dp[X][Y][S] := ( X, Y ) 지점에 상태 S로 도착하는데 필요한 최소한의 턴 수.

--> 현재 지점에서 nextX, nextY 로 이동할 때 Dp 값과 현재 시간을 비교해서 최소한의 턴 수 가 아니라면 더 탐색을 진행하지 않아도 된다.

 먼저 현재 지점에서 일반 이동을 해보고, 변신 상태가 아니라면 변신을 한 후 변신 이동을 해본다.

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

문제해석

 Green, Red 배양액을 땅에 뿌리고, 배양액이 주변으로 퍼져나가며, Green / Red 배양액이 만나게 되면 Flower가 생긴다.

문제핵심

1. 가능한 땅 중에서 Green, Red 배양액을 무조건 다 뿌려야 된다.

--> Backtracking 을 이용해서 가능한 모든 경우를 구해봐야 한다.

2. Green, Red 배양액이 단순히 만나는 게 아니라 동일한 시간에 도달한 땅에서만 Flower 가 생긴다.

--> 단순히 BFS 탐색만을 진행하면 안 된다.

알고리즘

1. 입력받은 map에서 배양액을 뿌릴 수 있는 vitaminMap을 따로 모아둔다.

2. 백트레킹을 통해 vitaminMap에 Green, Red 배양액을 다 뿌린다.

3. BFS 탐색을 통해서 Green, Red 배양액을 뿌려나갈 건데 다음과 같은 stateMap을 이용한다.

pair<int, int> stateMap[i][j] = (i, j) 에서 { 현재 시간, 현재 상태 } 를 저장한다.

--> 초기 배양액을 뿌린 곳들만 stateMap[i][j] = { 0, Green || Red } 로 초기화한다.

--> BFS 탐색을 통해서 현재 지점에서 다음 지점들로 탐색을 진행해나가는데, 

● 다음 지점의 stateMap 의 상태가 EMPTY 면 Green, Red 배양액이 아직 뿌려지지 않은 Map이므로 Green, Red 배양액을 저장해준다.

● 다음 지점의 stateMap 상태가 Green 이고 현재 상태가 Red 이고 같은 시간에 방문했다면 Flower 를 만듭니다.

● 다음 지점의 stateMap 상태가 Red 이고 현재 상태가 Green 이고 같은 시간에 방문했다면 Flower 를 만듭니다.

알고리즘회고

 처음에는 stateMap 을 이용할 생각을 못하고, 현재 queue에 저장된 Green, Red 에서 다음 지점들을 다 탐색해나가며 nextGreen, nextRed 라고 다음 지점들을 다 따로 저장했다. 그 후, 따로 저장한 지점들을 비교하며 Flower가 만들어지는 지점들을 체크하고 아닌 지점들은 다시 queue에 Push 해주는 방식으로 BFS 탐색을 진행했다. 당연히 시간이 위의 알고리즘에 비해 오래 걸렸고 BarkingDog 님의 코드를 참고해서 알고리즘을 개선할 수 있었다.

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

int N, M, G, R, ans;
int map[50][50]; // 0 은 호수 3은 레드 4는 그린
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
vector<pair<int, int>> vitaminMap;
int vitamin[10]; // 0은 아무것도 안뿌림 1은 레드 2는 그린

const int EMPTY = 0;
const int RED = 3;
const int GREEN = 4;
const int FLOWER = 5;

bool check(int r, int c) {
	if (0 <= r && r < N && 0 <= c && c < M) return true;
	return false;
}

void BFS() {
	int result = 0;
	pair<int, int> state[50][50];
	queue<pair<int, int>> q;
	for (int i = 0; i < vitaminMap.size(); i++) {
		if (vitamin[i] == 0) continue;
		state[vitaminMap[i].first][vitaminMap[i].second] = { 0, vitamin[i] };
		q.push(vitaminMap[i]);
	}
	while (!q.empty()) {
		int curX = q.front().first, curY = q.front().second;
		int curT = state[curX][curY].first, curC = state[curX][curY].second;
		q.pop();
		if (curC == FLOWER) continue;
		for (int dir = 0; dir < 4; dir++) {
			int nX = curX + dx[dir], nY = curY + dy[dir];
			if (!check(nX, nY)) continue; // 범위 밖
			if (map[nX][nY] == 0) continue; // 호수
			if (state[nX][nY].second == EMPTY) {
				state[nX][nY] = { curT + 1, curC };
				q.push({ nX, nY });
			}
			else if (state[nX][nY].second == RED) {
				if (curC == GREEN && state[nX][nY].first == curT + 1) {
					result++;
					state[nX][nY].second = FLOWER;
				}
			}
			else if (state[nX][nY].second == GREEN) {
				if (curC == RED && state[nX][nY].first == curT + 1) {
					result++;
					state[nX][nY].second = FLOWER;
				}
			}
		}
	}
	ans = max(ans, result);
	return;
}

void Backtracking(int s, int curG, int curR) {
	if (curG == G && curR == R) {
		BFS();
		return;
	}
	for (int i = s; i < vitaminMap.size(); i++) {
		if (vitamin[i] == 0 && curG < G) {
			vitamin[i] = GREEN;
			Backtracking(i + 1, curG + 1, curR);
			vitamin[i] = 0;
		}
		if (vitamin[i] == 0 && curR < R) {
			vitamin[i] = RED;
			Backtracking(i + 1, curG, curR + 1);
			vitamin[i] = 0;
		}
	}
	return;
}

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

	cin >> N >> M >> G >> R;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++){
			cin >> map[i][j];
			if (map[i][j] == 2) vitaminMap.push_back({ i, j });
		}

	Backtracking(0, 0, 0);

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

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

문제해석

 왼쪽끝에서 오른쪽끝으로 파이프를 연결해 길을 만들고 싶은데, 파이프끼리 겹치면 안되고 파이프는 오른쪽, 오른쪽 대각선 위, 오른쪽 대각선 아래 로 이어서 설치할 수 있다. 길을 최대 몇 개 만들 수 있을까?

문제핵심

 1. 현재 지점에서 파이프를 연결해 길을 만들 때, 아래에서 시작하는 다른 길과 겹치지않으려면 제일 좋은 이동은 오른쪽 대각선 위 > 오른쪽 > 오른쪽 대각선 아래 가 된다. 우리는 그냥 길을 최대한 많이 만들면 되므로 Greedy 하게 위에서부터 길을 만들어가면 된다.

 2. 일반적인 DFS 탐색은 탐색하고 돌아오면 visited 배열을 다시 초기화해주나, 이 문제에서는 방문해서 끝에 도달하지 못한 경로는 다른 지점에서 방문해도 어차피 끝에 도달하지 못하므로 visited 배열을 다시 초기화 해줄 필요가 없고, 초기화해준다면 경로가 겹쳐서 시간초과에 직면하게 됩니다.

알고리즘

 왼쪽 위에서부터 시작해서 DFS 탐색을 진행한다. 우선 순위가 높은 오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래 순으로 탐색을 진행하고 끝에 도달하게 된다면 S 지점에서 끝에 도달했다고 checked 를 한다. 그 후, S 지점에서 시작하던 탐색들을 다 종료한다. 재귀적으로 탐색을 하고 돌아왔다는 사실은 그 길로는 오른쪽 끝에 도달하지 못한다는 것을 의미한다. 따라서, visited 배열을 초기화하지 않고 그대로 남겨두어 다른 경로에서 이 지점을 탐색하는 불필요한 연산을 줄여주면 시간초과를 피할 수 있다.