굳건하게

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

기존풀이 :  https://travelbeeee.tistory.com/332

[ 알고리즘풀이 ]

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

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

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

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

 이때, 탐색을 하면서 Time 을 count 해주고, 앞으로 밟아야 하는 땅이 '0' 이라면, realTime을 Time 값으로 갱신해준다.

 기존의 코드는 현재 밟은 땅들이 모두 '2' 이고, 앞으로 탐색할 곳이 없을 때를 찾기 위해 bool check1, check2를 이용했다. 이 부분을 조금 더 간결하게 코딩하기 위해 실제로 내가 탐색하는데 필요한 realTime 과 그냥 탐색이 진행될 때마다 시간을 count 해주는 Time 변수 두 개를 이용했다. 코드가 실제로 눈에 띄게 짧아진 것은 아니지만 가독성 면에서 조금 더 간결한 코드이지않을까 싶다...!

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

#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 realTime = 0, time = 0, cnt = 0;
	while (!q.empty()) {
		int s = q.size();
		for (int i = 0; i < s; i++) {
			pair<int, int> cur = q.front();
			q.pop();
			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;
						q.push({ nextX, nextY });
						if (map[nextX][nextY] == 0) {
							cnt++;
							realTime = time + 1;
						}
					}
				}
			}
		}
		time++;
	}

	if (cnt == spaceCount)
		ans = min(ans, realTime);

	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 });
		}
	}

	Backtracking(0, 0);

	(ans == INF) ? cout << -1 : cout << ans;
}

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

[ 알고리즘풀이 ]

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

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

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

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

    '1' (벽) 이 아니라면 탐색을 진행하면 된다.

■ 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 = -1, cnt = 0;
	while (!q.empty()) {
		int s = q.size();
		for (int i = 0; i < s; i++) {
			pair<int, int> cur = q.front();
			q.pop();
			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;
						q.push({ nextX, nextY });
						if (map[nextX][nextY] == 0)
							cnt++;
					}
				}
			}
		}
		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 });
		}
	}

	Backtracking(0, 0);

	(ans == INF) ? cout << -1 : cout << ans;
}

문제 : 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;
}

[ 알고리즘풀이 ]

 우리는 주어진 skill_trees 중 skill 과 관련된 알파벳만 신경쓰면 되므로, 먼저 skill 을 순회하며 skill 에 나온 Alphabet을 체크한다. 그 후, skill_trees의 tree들을 모두 순회하며, pointer j 를 이용해 tree 중 우리가 신경써야되는 알파벳이 현재 주어진 skill 과 순서가 맞는지 확인하고 아니라면 다음 tree로 넘어간다.

#include <string>
#include <vector>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    bool checkAlphabet[26]={};
    for(int i = 0; i < skill.length(); i++)
        checkAlphabet[skill[i] - 'A'] = 1;
    
    for(int i = 0; i < skill_trees.size(); i++){
        bool check = true;
        int j = 0;
        for(int k = 0; k < skill_trees[i].length(); k++){
            if(!checkAlphabet[skill_trees[i][k] - 'A'])
                continue;
            if(skill[j] != skill_trees[i][k]){
                check = false;
                break;
            }
            j++;
        }
        if(check)
            answer++;
    }
    return answer;
}