언제나 처음처럼

[문제 링크]

왠지 영어로 된 알고리즘 문제를 풀어봐야 할 것 같아서 풀게되었다.

문제는 간단했다. 한 블록을 뒤집으면 상하좌우에 존재하는 블록들까지 동시에 뒤집어지는데, 모든 블록을 블랙 또는 화이트가 되도록 만들기 위해 뒤집는 최소한의 횟수를 구하는 문제였다.

최소한의 횟수를 구하기 위해 bfs를 구현하면 간단히 풀 수 있는 문제인데, 한가지 문제가 있다면 이전에 등장했던 보드판의 상태를 중복탐색 하는 것을 막기 위해 방문체크를 해줘야 하는데, 블록의 형태를 어떻게 표현할 것인지가 문제였다.

보드판은 항상 4x4 이므로 보드판에 존재하는 블록의 개수 또한 항상 16개라는 것을 알 수 있다.

따라서, 비트마스크 기법을 활용하면 보드판의 상태를 integer 타입의 정수형 데이터로 표현하는 것이 가능하다.

보드판의 좌표 (y,x)를 (4*y)+x 공식에 대입하여 자릿수를 구한 다음, OR 연산을 통해 해당 자릿수의 값을 블랙일 경우 1, 화이트일 경우 0으로 세팅하고, 공을 뒤집는 작업은 XOR 연산을 통해 값을 반전시켜줌으로써 간단하게 보드판을 관리할 수 있다.

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

int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };

int ptod(int y, int x) {
	return (y * 4) + x;
}

int bfs(int start) {
	int allBlack = (1 << 16) - 1;
	int allWhite = 0;
	bool visited[(1 << 16)] = { false };

	queue<pair<int, int>> q;
	q.push({ start,0 });
	visited[start] = true;

	while (!q.empty()) {
		int here = q.front().first;
		int round = q.front().second;
		q.pop();

		if (here == allBlack || here == allWhite)
			return round;

		for(int i=0; i<4; i++)
			for (int j = 0; j < 4; j++) {
				int there = here;
				there ^= (1 << (ptod(i, j)));

				for (int k = 0; k < 4; k++) {
					int nextY = i + dy[k];
					int nextX = j + dx[k];
					if (nextY >= 0 && nextY < 4 && nextX >= 0 && nextX < 4) {
						there ^= (1 << (ptod(nextY, nextX)));
					}
				}
				if (!visited[there]) {
					visited[there] = true;
					q.push({ there, round + 1 });
				}
			}
	}

	return -1;
}

int solution(vector<string>& input) {
	int inputNumber = 0;
	for(int i=0; i<4; i++)
		for (int j = 0; j < 4; j++) {
			int digit = ptod(i, j);
			if (input[i][j] == 'b')
				inputNumber |= (1 << digit);
		}

	return bfs(inputNumber);
}

int main(void) {
	vector<string> input;
	for (int i = 0; i < 4; i++) {
		string s;
		cin >> s;
		input.push_back(s);
	}

	int result = solution(input);
	if (result != -1)
		cout << result;
	else
		cout << "Impossible";

	return 0;
}

[문제 링크]

백트래킹과 BFS를 활용하여 풀 수 있는 문제였다.

입력으로 주어지는 바이러스들과 그 바이러스를 M개 활성화 시키는 모든 경우의 수를 백트레킹을 통해 완전탐색 하고, 모든 경우에 대해 바이러스를 확산시키는 BFS를 수행하여 가장 빠르게 확산되는 시간을 구해주면 원하는 결과를 얻을 수 있다.

시간이 0.25초로 제한되어 있기 때문에 2차원배열 전체를 순회하며 활성화 된 바이러스가 있는 위치를 찾아 확산시키는 방식으로 BFS를 구현하게 된다면 최악의 경우  (50^2) * (10개중 5개를 뽑는 조합의 수 252) * 50 =  31,500,000번 연산을 수행해야 하므로 제한 시간을 초과하게 된다. 따라서 배열 전체를 순회하는 방식이 아닌, 활성화 된 바이러스의 위치를 따로 저장하여 바이러스가 존재하는 좌표에 바로 접근할 수 있도록 구현하였다.

#include <iostream>
#include <cstring>
#include <queue>
#include <list>
using namespace std;

struct Pos {
	int y;
	int x;
};

const int INF = 987654321;
int N, M, cnt = 0, blank = 0;
int leastTime = INF;
int board[50][50];
Pos virus[10];

int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

int bfs(list<Pos> actVirus) {
	bool visited[50][50] = { false };
	for (auto x : actVirus)
		visited[x.y][x.x] = true;

	int change = 0;

	queue <int> q;
	q.push(0);

	while (!q.empty()) {
		int time = q.front();
		q.pop();

		if (change == blank) return time;
//		bool isChange = false;

		int listSize = actVirus.size();
		for (int i = 0; i < listSize; i++) {
			Pos here = actVirus.front();
			actVirus.pop_front();

			for (int j = 0; j < 4; j++) {
				int nearY = here.y + dy[j];
				int nearX = here.x + dx[j];
				if (nearY >= 0 && nearY < N && nearX >= 0 && nearX < N && !visited[nearY][nearX])
					if (board[nearY][nearX] == 2 || board[nearY][nearX] == 0) {
						visited[nearY][nearX] = true;
//						isChange = true;
						actVirus.push_back({ nearY, nearX });
						if (board[nearY][nearX] == 0)
							change++;
					}
			}
		}
//		if (isChange) q.push(time + 1);
		if (!actVirus.empty()) q.push(time + 1);
	}

	return INF;
}

void backtracking(int start, list<Pos>& actVirus) {
	int select = actVirus.size();
	if (select == M) {
		leastTime = min(leastTime, bfs(actVirus));
		return;
	}

	for (int i = start; i < cnt; i++) {
		Pos pos = virus[i];
		actVirus.push_back({ pos.y, pos.x });
		backtracking(i + 1, actVirus);
		actVirus.pop_back();
	}
}

int main(void) {
	cin >> N >> M;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
			if (board[i][j] == 2) {
				virus[cnt].y = i;
				virus[cnt].x = j;
				cnt++;
			}
			else if (board[i][j] == 0)
				blank++;
		}

	list<Pos> actVirus;
	backtracking(0, actVirus);

	if (leastTime == INF)
		cout << -1 << endl;
	else
		cout << leastTime << endl;

	return 0;
}

[문제 링크]

간단한 문제였다. 모든 정점을 시작점으로 bfs나 dfs를 수행하여 그중 최댓값을 찾으면 정답을 받을 수 있다.

하지만 이 문제를 더 빠르게 풀 수 있는 방법이 존재한다고 한다. 

뿌리노드인 1번 노드에서 가장 멀리 떨어진 정점을 찾고, 그 정점을 시작점으로 하여 가장 멀리 떨어진 정점까지의 거리가 곧 트리의 지름이 된다. 따라서 탐색을 2번 수행하므로 O(n) 시간에 문제를 해결할 수 있다.

자세한 증명은 구사과님의 블로그에 설명되어 있다.

https://koosaga.com/14

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

int N;
vector<vector<pair<int, int>>> adj(10001);
bool visited[10001];

pair<int, int> bfs(int start) {
	queue<pair<int, int>> q;
	q.push({ start, 0 });
	visited[start] = true;

	pair<int, int> ret = { 0,0 };
	while (!q.empty()) {
		int here = q.front().first;
		int cost = q.front().second;
		q.pop();

		if (ret.second < cost)
			ret = { here, cost };

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].first;
			int nextCost = cost + adj[here][i].second;

			if (!visited[there]) {
				visited[there] = true;
				q.push({ there, nextCost });
			}
		}
	}

	return ret;
}


int main(void) {
	cin >> N;
	
	for (int i = 0; i < N - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		adj[a].push_back({ b, c });
		adj[b].push_back({ a, c });
	}

	// find maximum node
	int maxNode = bfs(1).first;

	memset(visited, false, sizeof(visited));

	// get diameter
	int diameter = bfs(maxNode).second;

	cout << diameter << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 168 day