기록을

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

조합과 bfs가 합쳐진 문제인 연구소 시리즈의 첫번째 문제이다.

다른 연구소 문제를 해결했다면, 비슷한 아이디어로 무난하게 해결할 수 있다.

알고리즘은 다음과 같다.

1. 빈 공간(0인 위치)를 벡터에 모두 담아놓고 그 중 세개를 조합으로 뽑는다.

2. 조합으로 뽑은 곳의 값을 1로 (벽으로) 변경해준 이후에 bfs를 수행한다.

3. 방문되지 않은 지점(바이러스가 퍼지지 않은 지점)이면서 빈 공간인 부분의 수를 계산한다.

4. 수정한 map과 방문처리 배열을 초기화 시켜준다.

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

특별한 알고리즘이랄 것이 필요하지 않은 전형적인 시뮬레이션 문제였다.

하지만 설계를 제대로 하고 들어가지 않으면 꽤 해맬 수 있었던 문제이다.

여느 시뮬레이션 문제들이 그러하듯이, 상황을 어떻게 표현할 것인가 생각해야 한다.

나는 주의 깊게 그림을 살펴보지 않아서 간과했던 사실이지만, 문제 설명에서 그림을 보여주면서 좌표 값을 그림 아래에 표시해줬다.

그것을 보면, 커브의 상태를 좌표에 찍을 수 있고, 좌표에 어떻게 찍히느냐는 기본적으로 세대가 결정하고,

같은 세대라고 할지라도 시작한 방향값이 다르다면 다르게 찍힌다는 것을 알 수 있다.

(0,0)에서 시작한 0세대 커브는 (1,0)으로 x값이 1증가한다.

그리고 이어서 2세대로 변천할 때, 1세대의 마지막 점(1,0)에서 (1,-1)로 이동하여 y좌표가 1감소하는 것을 알 수 있다.

이 상황은 0,0에서 시작한 d값이 1인 0세대의 커브이다.

만약 나머지 조건이 동일하고, 방향 값인 d값이 1이었다면?  0,0에서 시작한 커브는 상단으로 뻗었을 것이고

0세대 커브는 0,0에서 0,-1로 변천했을 것이다. 이런식으로 파악해나가야 한다.

방향이 0인 세대별 커브의 성분을 방향 숫자로 나타내보면,

0세대: 0

1세대: 0, 1

2세대: 0, 1, 2, 1

3세대: 0, 1, 2, 1, 2, 3, 2, 1

4세대: 0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 0, 3, 2, 3, 2, 1

...

이런식으로 증가한다. 여기서 규칙을 확인할 수 있다. 먼저 개수가 2의 거듭제곱 꼴로 늘어나고 있다.

그리고 문제에서 주어진 조건과 연결해서 확인해보면, 이전 세대의 커브를 90도 돌리고 끝을 붙인다고 했다.

90도 돌린다는 것은 방향값의 변화를 의미하는 것이고, 끝을 붙인다는 것은, 성분을 뒤에서부터 하나씩 붙인다는 것이다.

따라서 0세대에서 1세대로 갈 때, 0에 1을 더한 1이 붙은 것이고, 1세대에서 2세대로 갈 때, 1세대의 마지막인 1에 1을 더한 값인 2가 붙고, 0에 1을 더한 값인 1이 그 뒤에 붙은 것이다.

이를 그냥 배열 인덱스로 조절해서 구해도 되겠지만 동작 구조가 스택과 같으니, 스택을 활용했다.

나는 방향 0의 드래곤커브의 10세대를 구해서 배열에 저장했다. 10세대를 구하면 곧, 앞부분에 0~9세대도 포함되어 있는 것이기 때문에 변형해서 사용하면 된다. 또한 방향 0의 값을 구해 놓았으니, 방향이 변하면 모든 성분을 더해줘서 방향을 바뀐 것처럼 사용하면 되고, %4를 통해 값이 4를 넘어가지 않도록 유지해줘야 하겠다.

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

비교적 간단한 조합 / 백트래킹 / 전수조사 문제이다.

문제를 보면, 결국 모든 경우의 수를 조사해야 하는 상황이다. 따라서 집의 위치와, 치킨집의 위치를 따로 벡터에 담아주고,

백트래킹을 활용해서 치킨집을 m개 선택한 다음, 선택한 치킨집을 가지고 치킨 거리를 구하면 되겠다.

이 경우에 다시 일반 가정집을 검색할 필요가 없도록, 미리 초반에 일반집도 벡터에 담아두고 사용하면 되겠다.

[소스코드]

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

연구소 3을 해결했다면 거저 먹을 수 있는 문제이다.

기본적으로 바이러스의 후보지들을 가지고 조합을 구해야 한다.

바이러스 후보지가 5곳이고 m = 3으로 주어진다면, 5Cm만큼의 경우의 수를 확인해보면 답을 찾을 수 있다.

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

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

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

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

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

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

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

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

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

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

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

bfs 혹은 dfs를 활용하여 해결할 수 있다.

인구이동 조건과, 방문 여부가 탐색 진행의 기준이 된다.

for(for(bfs)) 구조로 해결할 수 있다.

for(for 을 완전히 탈출할 때 까지가 한 번의 인구이동 날이라고 할 수 있다.

따라서 이를 무한루프로 감싸서, 인구의 이동이 없는 경우 무한루프를 탈출하는 구조로 해결하면 된다.

그런데, 인구 이동 조건을 만족하더라도, 그 자리에서 인구수를 바로 갱신할 수가 없다.

일단 국경을 개방할 수 있는 지점을 모두 찾아내야 하기 때문에, 일단 한 번의 bfs가 다 종료되어야 인구수를 갱신할 수 있다. 방문처리된 지점들(큐에 삽입된 적이 있는 지점들)이 갱신의 대상이기 때문에, 이 좌표들을 차례로 백터에 저장해준다.

이후에 벡터의 크기가 연합국의 숫자이고, 인구수의 합은 큐에 삽입하면서 기억해 둘 것이다.

한번의 인구 이동이 모두 끝났는데, 변화가 없다면 무한 루프를 종료하고, 그렇지 않다면 방문처리 배열을 초기화해준 이후에 인구이동을 다시 시작해주면 된다.

#include<iostream>
#include<queue>
#include<math.h>
#include<vector>
using namespace std;
int N, L, R, m[51][51];
bool bor[51][51]; //방문 처리 배열
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };

queue<pair<int, int> > q;
bool updated = false;
int idxSum = 0;
vector<pair<int, int> > v;
void bfs(pair<int, int> start) {
	q.push(start);
	bor[start.first][start.second] = true;

	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 || bor[nr][nc])
				continue;
			if (abs(m[nr][nc] - m[cur.first][cur.second]) >= L &&
				abs(m[nr][nc] - m[cur.first][cur.second]) <= R) {
				q.push({ nr, nc });
				bor[nr][nc] = true; 
				
				v.push_back({ nr, nc });
				idxSum += m[nr][nc];
			}
		}
	}
}
void init() {
	for (int i = 0; i < N; i++) 
		for (int j = 0; j < N; j++) 
			bor[i][j] = 0;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> m[i][j];

	int res = 0;
	while (1) {
		updated = false;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!bor[i][j]) {
					v.clear();
					v.push_back({ i,j }); 
					idxSum = m[i][j];
					bfs({ i, j });
				}
				//열린 국경이 있으면
				if (v.size() >= 2) { //한 연합 내의 국가 개수
					updated = true;
					int val = idxSum / v.size();
					for (int i = 0; i < v.size(); i++) {
						m[v[i].first][v[i].second] = val;
					}
				}
			}
		}
		if (updated) res++;
		else break;
		init();
	}
	cout << res << '\n';
	return 0;
}

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

선수 9명의 순서를 결정해야 한다. 4번 타자는 1번 선수로 고정되어 있기 때문에 이를 반영해준다.

이닝별로 선수들의 결과를 입력으로 받는다.

따라서 모든 순열을 구해서 선수들의 순서를 만들어낸 이후에, 야구의 조건을 구현해주면 된다.

1루, 2루 등에 진출해 있는 선수들에 대한 관리는, 선수 번호를 그대로 인덱스로 해서 배열을 두었다.

1이면 1루에 있다는 뜻이고, 2면 2루 3이면 3루에, 

4 이상이 되면 홈으로 들어왔다는 의미이다.

각 이닝별로 선수들의 수행을 그대로 따라가면서 시뮬레이션을 진행해주면 된다.

res[][] 배열은 이닝별 선수의 득점이다.

num은 1~9까지 선수들 중에 9명을 뽑는 경우의 수로 사용한다.

ord는 뽑아서 결정된 선수들의 순서이다. ord[i]는 i번 타자를 의미한다.

#include<iostream> //2백만
#include<vector>
using namespace std;
int n, res[52][10], num[10], ord[10], pos[10], Max = -1;
bool isused[10];
void play() {
	int hitter = 1, score = 0;
	for (int i = 1; i <= n; i++) { //i이닝에
		int outCnt = 0;

		while (1) {
			if (res[i][ord[hitter]] == 0) { //아웃인 경우
				hitter++;
				if (hitter >= 10) hitter = 1;
				outCnt++;
				if (outCnt == 3) {
					//이닝 교체
					for (int j = 1; j <= 9; j++) pos[j] = 0;
					break;
				}
			}
			else {
				//득점타
				for (int j = 1; j <= 9; j++) {
					if (pos[j] > 0 || j == ord[hitter]) { //타석에 나가 있는 선수라면
						pos[j] += res[i][ord[hitter]];
						if (pos[j] >= 4) {
							//홈에 들어오면
							pos[j] = 0;
							score++;
						}
					}
				}
				hitter++;
				if (hitter >= 10) hitter = 1;
			}
		}
	}
	if (Max < score) Max = score;
}
void func(int k) {
	if (k > 9) { //base condition
		play();
		return;
	}
	for (int i = 2; i <= 9; i++) {
		if (!isused[i]) {
			ord[k] = i;
			isused[i] = true;
			if (k == 3) func(k + 2); //3번엔 다음 4번이 아니라 5번을 정함
			else func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	for (int i = 1; i <= 9; i++)
		num[i] = i;
	isused[1] = true; //1은 항상 사용중
	ord[4] = 1; // 4번 선수는 항상 1
	cin >> n;
	
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= 9; j++) 
			cin >> res[i][j];
	
	func(1);
	cout << Max << '\n';
	return 0;
}

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

1차원에서 최단거리를 구하는 문제이고, 가중치가 없기 때문에 bfs를 활용해주면 된다.

움직임 배열을 입력받는 U와 D로 정해주고, 시작점을 큐에 넣은 이후에, 하나씩 pop 해서 확인해주면 된다.

#include<iostream>
#include<queue>
using namespace std;
int n, src, des, Up, Down;
int dis[1000001]; //1 indexed
int Move[2];
queue<int> q;
void bfs(int start) {
	q.push(start);
	dis[start]++;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = 0; i < 2; i++) {
			int nf = cur + Move[i];
			if (nf < 1 || nf > n || dis[nf] >= 0) continue;
			q.push(nf);
			dis[nf] = dis[cur] + 1;
		}
	}
}
int main(void) {
	
	cin >> n >> src >> des >> Up >> Down;
	for (int i = 1; i <= n; i++)
		dis[i] = -1;
	Move[0] = Up;
	Move[1] = Down * -1;
	bfs(src);
	if (dis[des] == -1) cout << "use the stairs\n";
	else
		cout << dis[des] << '\n';
	return 0;
}

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

먼저 주사위의 동, 서, 남, 북, 위, 아래를 배열 인덱스의 0~5까지로 대응시킨다.

명령을 하나씩 받아서, 먼저 이동할 수 있는지 판단한다. 동쪽이면 동쪽으로 벗어날 것이고, 남쪽이면 남쪽으로 벗어날 것이고 이런 식으로 확인할 수 있다.

지도를 벗어나지 않는다면, 명령에 맞춰서 주사위를 회전해주면 된다. 회전 방향에 따라 주사위의 상태를 갱신해주고, 주사위의 위치를 변경해준다.

이후에 조건에 맞게 출력을 해주면 된다.

#include<iostream>
using namespace std;
int dice[6];
int Row, Col, srcR, srcC, cnt, m[20][20];
void Move(int dir) {
	int temp;
	if (dir == 1) { //동쪽으로 굴릴 때
		if (srcC + 1>= Col) return;
		//주사위 회전, 좌표 이동
		//남2 북3 그대로
		temp = dice[0];
		dice[0] = dice[4];
		dice[4] = dice[1];
		dice[1] = dice[5];
		dice[5] = temp;
		srcC++;
	}
	else if (dir == 2) { //서
		if (srcC - 1 < 0) return;
		temp = dice[1];
		dice[1] = dice[4];
		dice[4] = dice[0];
		dice[0] = dice[5];
		dice[5] = temp;
		srcC--;
	}
	else if (dir == 3) { //북
		if (srcR - 1 < 0) return;
		temp = dice[3];
		dice[3] = dice[4];
		dice[4] = dice[2];
		dice[2] = dice[5];
		dice[5] = temp;
		srcR--;
	}
	else { //남
		if (srcR + 1 >= Row) return;
		temp = dice[2];
		dice[2] = dice[4];
		dice[4] = dice[3];
		dice[3] = dice[5];
		dice[5] = temp;
		srcR++;
	}
	if (m[srcR][srcC] == 0) {
		m[srcR][srcC] = dice[5];
	}
	else {
		dice[5] = m[srcR][srcC];
		m[srcR][srcC] = 0;
	}
	cout << dice[4] << '\n';
}
int main(void) {
	
	cin >> Row >> Col >> srcR >> srcC >> cnt;
	for (int i = 0; i < Row; i++) {
		for (int j = 0; j < Col; j++) {
			cin >> m[i][j];
		}
	}
	while (cnt--) {
		int op;
		cin >> op;
		Move(op);
	}
	return 0;
}

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

arr[0]에 공이 있다고 정해둔다.

arr에 1,2,3을 초기에 순서대로 담아두고, 값이 컵의 번호라고 생각하고 들어오는 숫자의 인덱스를 구해서 두 인덱스에 해당하는 arr값을 스왑해준다.

#include<iostream>
using namespace std;
int m, arr[3] = { 1,2,3 };
int main(void) {
	cin >> m;

	while (m--) {
		int num1, num2, idx1, idx2;
		cin >> num1 >> num2;
		for (int i = 0; i < 3; i++) {
			if (arr[i] == num1) idx1 = i;
			if (arr[i] == num2) idx2 = i;
		}
	
		int temp = 0;
		temp = arr[idx1];
		arr[idx1] = arr[idx2];
		arr[idx2] = temp;
	}
	cout << arr[0] << '\n';

	return 0;
}