기록을

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

문제 설명

1. 비활성 바이러스의 위치가 여러곳 주어진다.

2. 그 중에서 M개를 선택해서 확산 바이러스로 만들고, 바이러스의 확산을 시작한다.

(확산 바이러스는 비활성 바이러스를 만나면 그 비활성 바이러스를 확산 바이러스로 바꾼다)

3. 바이러스가 전부 퍼질 때까지 걸린 시간의 최솟값을 구하여라.

문제를 시작하기 전에 몇가지 표현을 잘 이해하고 들어가야한다.

먼저 문제가 구하라고 한 것은, 바이러스가 다 퍼질 때까지 걸린 최소 시간이다. 퍼지는 바이러스가 활성 바이러스여야 한다는 말은 없다.

테스트케이스를 좋게 주지 않았더라면 괴랄한 정답률을 보여주지 않았을까 생각한다.

아래쪽에 있는 테스트 케이스를 활용하면 대부분의 엣지 케이스에 대한 감을 잡을 수 있을 것이다.

[알고리즘]

1. 백트레킹을 활용해서 전체 바이러스 중에서 m개를 선택한다.

2. 선택한 m개의 바이러스를 큐에 넣고 BFS를 돌린다.

3. 빈칸과 비활성 바이러스가 있으면서 방문하지 않은 지점이면 바이러스를 확산시키고, 시간을 기록한다.

4. 시간이 얼마 걸렸는지 파악하기 위해 방문처리 배열 내에서 최댓값을 찾는다. 이 때 최댓값을 선택할 때 그 지점이 바이러스가 위치하고 있는 지점이라면 최댓값으로 보지 않는다.

마지막 테스트 케이스에서와 같이, 이미 바이러스로 채워져있는 곳은 사실 방문할 필요가 없었던 지점이다. 하지만 거쳐가면서 확산이 이루어져야 하기 때문에 일단 채택은 하고, 바이러스가 전체로 퍼지는 시간에는 영향을 끼치면 안되기 때문에 제외해준다.

5. 위에서 구한 최댓값(시간)의 최솟값을 답으로 정한다.

#include<iostream>
#include<vector>
#include<queue>
#include<limits.h>
using namespace std;

int n, m, map[51][51], dis[51][51], arr[11], st = 0; //연구소 크기, 바이러스 개수
bool isused[11];
struct VIRUS {
	int r;
	int c;
};
vector<VIRUS> v;
queue<pair<int, int> > q;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int res = INT_MAX;

void bfs() {
	
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		
		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];
			if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
			if (dis[nr][nc] >= 0 || map[nr][nc] == 1) continue;
			
			q.push({ nr, nc });
			dis[nr][nc] = dis[cur.first][cur.second] + 1;
		}
	}
}
void init() {
	for(int i = 0 ; i < n ; i++)
		for (int j = 0; j < n; j++) 
			dis[i][j] = -1;
}
bool isDone(){
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dis[i][j] == -1 && map[i][j] != 1)
				return false;
		}
	}
	return true;
}
void findMax() {
	int Max = 0;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			if (Max < dis[i][j] && map[i][j] != 2) 
				Max = dis[i][j];

	if (res > Max) res = Max;
}
void func(int k) {
	if (k == m) {

		for (int i = 0; i < m; i++) {
			int r = v[arr[i]].r;
			int c = v[arr[i]].c;
			q.push({ r, c });
			dis[r][c]++;
		}
		bfs();

		if (isDone()) 
			findMax();
		
		init();

		return;
	}

	if (k == 0) st = 0;
	for (int i = st; i < v.size(); i++) {
		if (!isused[i]) {
			arr[k] = i;
			st = i;
			isused[i] = true;
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			dis[i][j] = -1;
			if (map[i][j] == 2) { //바이러스 위치 저장
				VIRUS tmp;
				tmp.r = i;
				tmp.c = j;
				v.push_back(tmp);
			}
		}

	func(0);

	if (res == INT_MAX) cout << -1 << '\n';
	else
		cout << res;
	return 0;
}

https://www.acmicpc.net/problem/17143

필요한 상어에 대한 정보를 담아서 구조체를 만든다.

이후에는 착실하게 시뮬레이션을 진행해주면 된다.

나 같은 경우에는 이전에 나무재테크 문제를 풀 때를 떠올려서, 한 칸에 상어가 여러 마리 들어가는 경우가 생기기 때문에 배열로 벡터를 잡았다.

먼저 상어의 이동과 관련된 구현이다.

문제에서 상어의 속력은 1000까지 가능하다고 했는데, 이 부분에서 나름 연산의 횟수를 줄여보겠다고 행과 열의 길이를 활용해서 모듈러 연산을 사용했다.

그런데 생각하지 못한 부분이 있었어서 프린트를 찍어가며 디버깅을 하는 데에 애를 먹었다.

그냥 속편하게 속도만큼 반복문을 돌리면서 (완벽한 통제를 위해서 for문을 사용하는 것이 낫겠다) 속도만큼 칸을 이동해주고, 이동한 칸이 범위를 벗어난다면 다시 바로잡아주는 식으로 하는 것이 조금 더 쉽고 직관적으로 구현할 수 있는 방법인 것 같다.

다른 부분은 상어가 먹히는 부분이다.

나는 일단 상어는 다 칸에 들어갈 수 있고, 그 이후에 가장 큰 상어를 찾아서 그 상어만 두고 나머지 상어는 다 제거하는 방식으로 구현을 했다.

간단하게 auto를 사용하지 않고, iterator를 선언하는 방법과, 이를 이용해서 출력하는 것을 코드로 나타내었다.

내용은 향후에 추가될 예정이다.

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

int main(void) {

	list<int> L = { 1, 2 };
	list<int>::iterator it = L.begin(); //iterator를 포인터라고 생각하면 편하다
	
	cout << *it << '\n';
	L.push_back(3);
	it++;
	it++; //한칸씩 움직인다
	cout << *it << '\n'; //3을 가리킴

	//여기까지 1,2,3

	L.insert(it, 10); //it는 3 가리키고있었는데 왼쪽에 10이 추가됨. it는 여전히 3 가리킴

	L.insert(it, 15); //3가리키는 it왼쪽에 15추가

					  //전체 리스트 출력
	for (list<int>::iterator itor = L.begin(); itor != L.end(); itor++) {
		cout << *itor << ' ';
	}
	
	cout <<'\n' << *it << '\n';

	it = L.erase(it);
	it--;

	
	for (list<int>::iterator itor = L.begin(); itor != L.end(); itor++) {
		cout << *itor << ' ';
	}

	cout << '\n' << *it << '\n';

	it = L.end(); // 리스트의 끝보다 한칸 더 오른쪽의 값을 가리킨다
	it--; //그러니까 하나 당겨주고 
	cout << '\n' << *it << '\n'; //출력해야 마지막 값이 나온다

	it = L.begin();
	cout << '\n' << *it << '\n'; //처음 값
	return 0;
}

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

특별한 알고리즘이랄 것이 없지만, 벡터를 활용하는 약간의 센스가 필요하다.

정수를 담는 벡터 자료형을 이차원 배열로 선언한다.

그래야 이차원 좌표상의 한 공간에 나무가 여러개 쌓이는 효과를 볼 수 있다.

그리고, 여름에 나무의 삭제가 발생할 때, 삭제되는 나무에 대한 처리를 할 때, vector.erase를 사용하고, 삭제되는 나무들에 대한 정보를 큐로 옮긴 이후에, 큐에서 pop하면서 처리를 해서 시간초과를 받았다.

이를 해결하기위해서, 봄에 땅으로부터 영양분을 흡수하는 것은 어짜피 나무가 나이로 정렬된 상태로 이루어지고, 특정 나이가 땅의 양분보다 많은 순간이 온다면, 그 나무보다 나이가 많은 나무들은 자연스럽게 확인할 가치가 없어지기 때문에, 봄에 영양분을 흡수했던 나무들을 임시 벡터에 넣어두고, 실패지점 이후에 원본 벡터를 clear한 이후에, 임시 벡터에 들어있는 데이터를 원래 벡터에 옮겨주면 여름에 대한 구현을 할 수 있다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll grd[11][11];
int igr[11][11], n, m, k;
vector<ll> v[11][11];
int dr[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dc[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int main(void) {
	//1-indexed
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> igr[i][j];
			grd[i][j] = 5;
		}
	}
	for (int i = 1; i <= m; i++) {
		int r, c, age;
		cin >> r >> c >> age;
		v[r][c].push_back(age);
	}
	for (int i = 1; i <= k; i++) {
		//봄
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (v[i][j].size() > 0) { //i행 j열에 나무가 존재하면
					vector<ll> tmp;
					sort(v[i][j].begin(), v[i][j].end()); //어린 나무부터
					//땅양분이 나이보다 많으면 나이 증가, 땅 양분 감소
					ll dead = 0;
					for (int t = 0; t < v[i][j].size(); t++) {
						if (v[i][j][t] <= grd[i][j]) {
							tmp.push_back(v[i][j][t] + 1);
							grd[i][j] -= v[i][j][t];
						}
						else {
							dead += v[i][j][t] / 2;
						}
					}
					//여름
					v[i][j].clear();
					v[i][j] = tmp;
					grd[i][j] += dead;
				}
			}
		}

		//가을
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (v[i][j].size() > 0) {
					for (int t = 0; t < v[i][j].size(); t++) {
						if (v[i][j][t] % 5 == 0) {
							for (int ii = 0; ii < 8; ii++) {
								int nr = i + dr[ii];
								int nc = j + dc[ii];
								if (nr < 1 || nc < 1 || nr > n || nc > n) continue;
								v[nr][nc].push_back(1);
							}
						}
					}
				}
			}
		}

		//겨울
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				grd[i][j] += igr[i][j];
			}
		}
	}
	ll cnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (v[i][j].size() > 0) cnt += v[i][j].size();
		}
	}
	cout << cnt;
	return 0;
}

가령 X & Y 라는 수식이 있다고 하자. 이 때 &자리에는 | 그리고 ^도 올 수 있다.

순서대로 and, or, xor을 의미한다.

X와 Y를 이진수로 바꾸고, 각 자릿수의 비트를 해당 연산자에 맞게 연산해서 그 결과를 반환해준다.

일반 연산보다 연산 속도가 빠르다.

가령 2 & 3을 계산한다고 하면, 2는 이진수로 0000010, 3은 00000011이다.

왼쪽의 6자리 0끼리는 and 연산해봐야 0이므로 놔두고, 1 & 1 = 1, 0 & 1 = 0이기 때문에, 연산의 결과는

00000010 = 십진수로 2라고 할 수 있다.