굳건하게

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

[ 알고리즘풀이 ]

■ 연구소의 사이즈는 N, 바이러스의 개수는 M ( map을 입력받으면서 '0' 인 공간을 미리 count 해둔다. )

■ 바이러스를 M개 뽑아서 감염을 확산시킬 것이므로, 바이러스의 위치를 vir 에 저장한다.

■ Backtracking 을 이용해 vir에 저장된 바이러스 중 M개를 뽑는다.

■ 뽑힌 M개의 바이러스를 BFS 탐색을 이용해 감염을 확산시킨다. ( '0' 인 공간을 탐색하면 count )

 이때, 현재 Queue에 담겨있는(현재 탐색된 위치)가 모두 '2' 이고, 앞으로 탐색할 곳이 없다면 우리는 굳이 탐색하지 않아도 되는 비활성 바이러스들의 위치만 탐색한 것이므로, 탐색을 그전에 끝냈어야 한다. 따라서 time을 갱신하지 않고, BFS탐색을 break 한다. 그게 아닌 경우는 모두 감염이 진행되는데 필요한 시간이므로 time++ 을 통해 시간을 체크한다.

■ BFS 탐색을 하며 count 한 값과 (1) 에서 count 한 값을 비교해 모든 지역에 감염이 진행되었다면, 답을 갱신한다.

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#define INF 987654321

using namespace std;

vector<pair<int, int>> vir;
int N, M, spaceCount, ans = INF, map[50][50], dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
bool choice[10];

void spreadVirus(void) {
	bool visited[50][50] = {};
	queue<pair<int, int>> q;
	for (int i = 0; i < vir.size(); i++)
		if (choice[i]){
			q.push({ vir[i].first, vir[i].second });
			visited[vir[i].first][vir[i].second] = 1;
		}
	int time = 0, cnt = 0;
	while (!q.empty()) {
		bool check1 = false, check2 = false;
		int s = q.size();
		for (int i = 0; i < s; i++) {
			pair<int, int> cur = q.front();
			q.pop();
			if (map[cur.first][cur.second] == 0)
				check1 = true;
			for (int j = 0; j < 4; j++) {
				int nextX = cur.first + dx[j], nextY = cur.second + dy[j];
				if (0 <= nextX && nextX < N && 0 <= nextY && nextY < N) {
					if (map[nextX][nextY] != 1 && !visited[nextX][nextY]) {
						visited[nextX][nextY] = 1;
						check2 = true;
						q.push({ nextX, nextY });
						if (map[nextX][nextY] == 0)
							cnt++;
					}
				}
			}
		}
		if (check1 == false && check2 == false) // 기존에 다 '2'를 밟고, 지금은 밟은게 없다.
			break;
		else
			time++;
	}
	if (cnt == spaceCount)
		ans = min(ans, time);
	return;
}

void Backtracking(int s, int cnt) {
	if (cnt == M) {
		spreadVirus();
		return;
	}
	for (int i = s; i < vir.size(); i++) {
		choice[i] = true;
		Backtracking(i + 1, cnt + 1);
		choice[i] = false;
	}
}

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 < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 0)
				spaceCount++;
			if (map[i][j] == 2)
				vir.push_back({ i, j });
		}
	}

	if (spaceCount == 0)
		ans = 1;
	else
		Backtracking(0, 0);

	if (ans == INF)
		ans = 0;
	cout << ans - 1;
}

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

[ 알고리즘풀이 ]

 기존의 삼성 기출 문제처럼 모든 경우에 대해서 Backtracking을 통해 사다리를 조작하면 시간초과에 걸리게 되는 문제다. 

정의

ladder[a][b] : a번 가로선에서 b ~ b + 1 번 새로 선에 사다리가 연결되어있으면 1, 아니면 0.

1. 사다리를 우리는 최대 3개까지 조작할 수 있으므로, 0개부터 3개까지 조작하는 수를 하나씩 늘려가며 Backtracking 을 통해 조작하는 경우의 수를 구한다.

 ( 이때, 앞에서 조작으로 답이 갱신되었다면, 조작하는 수를 늘려가는 것은 의미가 없으므로 게임을 종료한다. )

2. Backtracking 을 통해 조작할 사다리를 정해야 한다. 이때, ladder[a][b] 에 사다리를 연결하려면, ladder[a][b - 1], ladder[a][b], ladder[a][b + 1] 이 모두 사다리가 없어야만 한다. 또, i번 가로선에서 사다리를 조작했다면, 그다음 조작할 사다리는 i번 가로선부터 다시 찾아가면 되므로 ( 즉, i번 보다 작은 쪽에서 사다리를 조작하는 경우는 이미 앞의 Backtracking 을 통해 계산하였으므로 ) Backtracking 인자에는 가로선 i 와 내가 조작할 사다리의 개수, 조작한 사다리의 개수를 인자로 넘겨준다.

3. 조작할 사다리의 개수와 조작한 사다리의 개수가 같다면 사다리 게임을 진행해 i번 째 사다리가 i 번에서 끝나는지 check 한다.

# 2번 과정에서 가로선을 인자로 넘겨주지 않고, 사다리를 다시 처음부터 순회하며 Backtracking을 진행해 시간 초과를 받았다.

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

#define INF 987654321
using namespace std;

int N, M, H, a, b, ans = 987654321;
bool ladder[31][11];

bool checkGame() {
	for (int k = 1; k <= N; k++) {
		int i = 1, j = k;
		while (i <= H) {
			if (ladder[i][j])
				j++;
			else if (ladder[i][j - 1])
				j--;
			i++;
		}
		if (j != k)
			return false;
	}
	return true;
}

void Backtracking(int row, int goal, int cnt) {
	if (ans != INF)
		return;

	if (goal == cnt){
		if (checkGame())
			ans = goal;
		return;
	}

	for (int i = row; i <= H; i++) {
		for (int j = 1; j < N; j++) {
			if (ladder[i][j - 1] == 0 && ladder[i][j] == 0 && ladder[i][j + 1] == 0) {
				ladder[i][j] = 1;
				Backtracking(i, goal, cnt + 1);
				ladder[i][j] = 0;
			}
		}
	}
	return;
}

void Init(void) {
	for (int i = 0; i <= 3; i++) {
		if (ans != INF)
			break;
		Backtracking(1, i, 0);
	}
}

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

	cin >> N >> M >> H;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		ladder[a][b] = 1;
	}

	Init();

	if (ans == INF)
		ans = -1;
	cout << ans;
}

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

[ 알고리즘풀이 ]

 S층에서 시작해 +U 층, - D층 BFS 탐색을 통해서 갈 수 있는 모든 층들에 대해서 필요한 최소 버튼을 갱신해나가면 된다.

#include<iostream>
#include<queue>

using namespace std;

int F, S, G, U, D, arrived[1000001];

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

	cin >> F >> S >> G >> U >> D;

	for (int i = 0; i <= F; i++)
		arrived[i] = -1;

	queue<pair<int, int>> Q;
	Q.push({ S, 0 });
	arrived[S] = 0;

	while (!Q.empty()) {
		pair<int, int> temp = Q.front();
		Q.pop();
		int curF = temp.first, curB = temp.second;
		if (curF == G)
			break;
		if (curF + U <= F) {
			if (arrived[curF + U] == -1) {
				Q.push({ curF + U, curB + 1 });
				arrived[curF + U] = curB + 1;
			}
		}
		if (curF - D >= 1) {
			if (arrived[curF - D] == -1) {
				Q.push({ curF - D, curB + 1 });
				arrived[curF - D] = curB + 1;
			}
		}
	}

	if (arrived[G] == -1)
		cout << "use the stairs";
	else
		cout << arrived[G];
}

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

[ 알고리즘풀이 ]

1. 윷놀이 판을 나타내는 road를 바깥외곽으로 도는 길, 10을 만나서 꺾이는 길, 20을 만나서 꺾이는 길, 30을 만나서 꺾이는 길, 25를 만나서 꺾이는 길, 마지막 40 으로 총 6가지 길로 표현한다.

2. 백트레킹을 이용해 4가지의 말을 움직이는 순서에 대한 모든 경우의 수를 구한다.

3. 말을 움직여 게임을 진행한다.

- 현재 움직일 말이 이미 도착 지점을 지난 경우는 진행되면 안되는 게임이므로 게임을 멈춘다.

- 현재 말의 위치가 10, 20, 30이면(파란색윳놀이판) 다른 road로 바꿔준다.

- 말을 움직이는데 움직였을 때, 해당 road를 벗어난다면 새로운 road로 길을 바꿔주고 아니라면 그냥 진행한다.

( 이때, 한 번에 두 가지 road를 건너뛰는 경우가 있으므로 주의해야한다. 예를 들어 road[0] 윳놀이판 '10' 에서 5칸을 지나가면 road[1] '13', '16', '19' 를 다 지나고 road[4] 로 넘어가야한다. )

- 움직인 말이 다른 말과 윳놀이 판에서 겹친다면 게임을 끝내고, 아니라면 합을 더해준다.

( check배열은 현재 윳놀이 판 해당 지점에 말이 있는지 없는지, checkHorse는 i번 째 말이 도착지점을 지나갔는지를 나타낸다. ) 

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

using namespace std;

int road[6][30] = {
	{0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, },
	{13, 16, 19, },
	{22, 24,},
	{28, 27, 26,},
	{25,30,35,},
	{40,}
};

int dice[10], ans = -1, maxLength[6] = { 20, 3, 2, 3, 3, 1 };

void playGame(vector<int> v) {
	bool check[6][30] = {};
	bool checkHorse[4] = {};
	pair<int, int> horse[4] = { {0, 0}, {0, 0}, {0, 0}, {0, 0} };
	int sum = 0;

	for (int i = 0; i < 10; i++) { // v[i]번째 말 선택, dice[i]만큼이동.
		if (checkHorse[v[i]]) // 지금 움직일 말이 이미 도착선을 지남 --> 그런 경우는 Pass
			return;

		check[horse[v[i]].first][horse[v[i]].second] = false; // 이동할것이므로 check 해제.
		// 이동하기전에 길이 바뀌는 경우 셋팅
		if (horse[v[i]].first == 0 && horse[v[i]].second == 5)
			horse[v[i]].first = 1, horse[v[i]].second = -1;
		else if (horse[v[i]].first == 0 && horse[v[i]].second == 10)
			horse[v[i]].first = 2, horse[v[i]].second = -1;
		else if (horse[v[i]].first == 0 && horse[v[i]].second == 15)
			horse[v[i]].first = 3, horse[v[i]].second = -1;

		// 이동하자.
		if (horse[v[i]].second + dice[i] >= maxLength[horse[v[i]].first]) { // 해당 길이 끝나서 다른 길로 가야됨.
			if (horse[v[i]].first == 0 || horse[v[i]].first == 4) {
				horse[v[i]].second = dice[i] - (maxLength[horse[v[i]].first] - horse[v[i]].second);
				horse[v[i]].first = 5;
			}
			else if (horse[v[i]].first == 5)
				checkHorse[v[i]] = true;
			else {
				horse[v[i]].second = dice[i] - (maxLength[horse[v[i]].first] - horse[v[i]].second);
				horse[v[i]].first = 4;
			}
			// 다른 길로 갔는데도 또 넘어가는 경우!
			if (horse[v[i]].second >= maxLength[horse[v[i]].first]) {
				if (horse[v[i]].first == 4) {
					horse[v[i]].second = horse[v[i]].second - maxLength[horse[v[i]].first];
					horse[v[i]].first = 5;
				}
				else if(horse[v[i]].first != 5){
					horse[v[i]].second = horse[v[i]].second - maxLength[horse[v[i]].first];
					horse[v[i]].first = 4;
				}
			}
		}
		else
			horse[v[i]].second += dice[i];

		// 이동했는데 이미 말이 있는 경우.
		if (check[horse[v[i]].first][horse[v[i]].second])
			return;
		// 말이 도착지점 밖으로 나가지 않았더라면 값 sum
		if (!checkHorse[v[i]]) {
			check[horse[v[i]].first][horse[v[i]].second] = true;
			sum += road[horse[v[i]].first][horse[v[i]].second];
		}
	}
	ans = max(ans, sum);
	return;
}

void Backtracking(vector<int> v) {
	if (v.size() == 10) {
		playGame(v);
		return;
	}
	for (int i = 0; i < 4; i++) {
		v.push_back(i);
		Backtracking(v);
		v.pop_back();
	}
	return;
}

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

	for (int i = 0; i < 10; i++)
		cin >> dice[i];
	vector<int> v;
	Backtracking(v);

	cout << ans;
}