백준 알고리즘 중급 - BFS (연습) - 1

Search Search

점점 업로드 주기가 길어진다..

좀 게을러진 것 같아 반성이 된다. 좀 더 마음을 다잡고 다시 해보자.

중요한 건 속도가 아니고 방향이니, 너무 성급해하지는 말고. 어쩌라는겨

아무튼 정리 시작!

-

* 뱀과 사다리 게임 (mid) : 변칙 조건이 주어진 보드판에서 도착점에 도달하는 최소 주사위 굴리기 횟수를 구하는 문제.

16928번: 뱀과 사다리 게임

- 뱀이 있는 칸에 가면 뒤로 가고, 사다리가 있는 칸에 가면 앞으로 간다. 100번 칸에 가기 위한 최소 횟수를 구하면 된다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool check[101];
int n, m;

int check_event(int x, vector <pair<int, int> > &lad, vector <pair<int, int> > &snake) {
	for (int i = 0; i < n; i++) {
		if (lad[i].first == x) {
			return lad[i].second;
		}
	}
	for (int i = 0; i < m; i++) {
		if (snake[i].first == x) {
			return snake[i].second;
		}
	}
	return x;
}

int bfs(vector <pair<int, int> > &lad, vector <pair<int, int> > &snake) {
	queue<pair<int, int> > q;
	q.push(make_pair(1,0));
	check[1] = true;

	int ans = -1;
	while (!q.empty()) {
		int x = q.front().first;
		int cnt = q.front().second;
		q.pop();
		for (int i = 1; i <= 6; i++) {
			int num = x + i;
			if (num < 100) {
				num = check_event(num, lad, snake);
				if (check[num] == false) {
					q.push(make_pair(num, cnt + 1));
					check[num] = true;
				}
			}
			else if (num == 100) {
				if (ans == -1 || ans > cnt + 1)
					ans = cnt + 1;
			}
		}
	}
	return ans;
}

int main()
{
	cin >> n >> m;

	vector <pair<int, int> > lad;
	int x, y;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		lad.push_back(make_pair(x, y));
	}

	vector <pair<int, int> > snake;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		snake.push_back(make_pair(x, y));
	}

	cout << bfs(lad, snake) << '\n';

	return 0;
}

- 사다리와 뱀을 입력 받고 bfs를 돌린다. 주사위로 나올 수 있는 1~6의 경우를 모두 생각해서 이동하고, 뱀이나 사다리가 있는지 확인한 뒤에 최종 이동 값을 구해주면 된다. 차근차근 따라가면 풀 수 있는 문제였다.

 

* 데스 나이트 (mid) : 업그레이드된 나이트인 데스 나이트를 이용해 특정 위치에 도달하는 최소 이동 횟수 구하기.

16948번: 데스 나이트

- 고려할 경우가 좀 더 많은 미로 찾기 문제라고 생각하면 된다. bfs로 어렵지 않게 풀 수 있었다.

#include <iostream>
#include <queue>

using namespace std;

int mx[] = { -2, -2, 0, 0, 2, 2 };
int my[] = { -1, 1, -2, 2, -1, 1 };

int n, r1, c1, r2, c2;
int dist[200][200];
bool check[200][200];

int bfs() {
	queue<pair<int, int> > q;
	q.push(make_pair(r1, c1));
	check[r1][c1] = true;
	dist[r1][c1] = 0;
	
	while (!q.empty()) {
		int tx = q.front().first;
		int ty = q.front().second;
		q.pop();
		for (int i = 0; i < 6; i++) {
			int x = tx + mx[i];
			int y = ty + my[i];
			if (x >= 0 && x < n && y >= 0 && y < n) {
				if (check[x][y] == false) {
					q.push(make_pair(x, y));
					check[x][y] = true;
					if (dist[x][y] == -1 || dist[x][y] > dist[tx][ty] + 1)
						dist[x][y] = dist[tx][ty] + 1;
				}
			}
		}
	}
	return dist[r2][c2];
}

int main()
{
	cin >> n;	
	cin >> r1 >> c1 >> r2 >> c2;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dist[i][j] = -1;
		}
	}

	cout << bfs() << '\n';
	
	return 0;
}

- dist 배열을 선언해서 해당 위치까지의 최소 이동 횟수를 구해준다. while문을 다 돌고 dist[r2][c2]를 구하면 바로 답이 나온다.

 

* DSLR (mid) : 단순히 최솟값만 구하는 게 아니라, 이동한 경로까지 구해야 하는 문제다.

9019번: DSLR

- D, S, L, R 각각이 갖는 계산 과정이 존재한다. 이 4가지 방법을 이용해 주어진 값 a에서 b까지 가는데 걸리는 최소 경로를 구하면 된다. 단순히 횟수만 구하는 게 아니라 어떤 계산 과정을 거쳤는지까지 고려해줘야 한다.

- 모범 답안에서는 from, how 라는 배열을 선언해 from[i] = j 는 i를 j로 만든 경우, how[i] = j 는 i를 만드는데 j 연산을 사용했다는 것을 표시해줬다. 근데 나는 그냥 연산값을 string으로 붙여버리고, string 길이를 비교해서 최솟값을 구했다. 이렇게 해도 속도 차이는 얼마 안 나더라. 그래도 깔끔한 풀이는 모범답안이니 숙지는 해두자. 아래는 내가 짠 코드.

#include <iostream>
#include <queue>
#include <string>

using namespace std;

string bfs(int a, int b) {
	queue<int> q;
	bool check[10001] = { false, };
	string dist[10001];
	q.push(a);
	check[a] = true;

	while (!q.empty()) {
		int tx = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int x;
			if (i == 0) {
				x = tx * 2;
				if (x > 9999) x %= 10000;
				if (check[x] == false) {
					q.push(x);
					check[x] = true;
					if (dist[x].empty() || dist[x].size() > dist[tx].size() + 1)
						dist[x] = dist[tx] + 'D';
				}
			}
			else if (i == 1) {
				x = tx - 1;
				if (x < 0) x = 9999;
				if (check[x] == false) {
					q.push(x);
					check[x] = true;
					if (dist[x].empty() || dist[x].size() > dist[tx].size() + 1)
						dist[x] = dist[tx] + 'S';
				}
			}
			else if (i == 2) {
				x = tx;
				x = (x % 1000) * 10 + x / 1000;
				if (check[x] == false) {
					q.push(x);
					check[x] = true;
					if (dist[x].empty() || dist[x].size() > dist[tx].size() + 1)
						dist[x] = dist[tx] + 'L';
				}
			}
			else if (i == 3) {
				x = tx;
				x = (x % 10) * 1000 + (x / 10);
				if (check[x] == false) {
					q.push(x);
					check[x] = true;
					if (dist[x].empty() || dist[x].size() > dist[tx].size() + 1)
						dist[x] = dist[tx] + 'R';
				}
			}
			if (x == b)
				return dist[b];
		}
	}
}

int main()
{
	int t;
	cin >> t;

	while (t--) {
		int a, b;
		cin >> a >> b;

		cout << bfs(a, b) << '\n';
	}

	return 0;
}

- 이 문제가 갖는 또 하나의 포인트는, 자리수 이동을 계산하는 것이었다. 나누기, 나머지 연산을 이용해서 왼쪽, 오른쪽 자리 이동을 구현 해야했다. 나머지는 조건에 맞춰서 계산해주기만 하면 큰 문제는 없었다.

 

* 연구소 (mid) : 바이러스가 최소한으로 퍼지도록 벽을 쌓고, 청정 구역의 최댓값을 구하는 문제였다.

14502번: 연구소

- 지도를 일일이 바꿔 가면서 풀면 복잡해지니까, 원래 지도는 놔두고 따로 배열을 선언해 방문을 체크해줬다. 벽을 새로 세울 때마다 경우를 따져줘야 하니까, 시기 적절한 초기화도 중요한 포인트였다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;
int map[8][8];
bool visit_wall[8][8];
bool init_virus[8][8];
queue <pair<int, int> > v;

int mx[] = { 1,-1,0,0 };
int my[] = { 0,0,1,-1 };

int ans = -1;
void go(int cnt) {
	if (cnt == 3) {
		queue <pair<int, int> > q = v;
		bool virus_check[8][8];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				virus_check[i][j] = init_virus[i][j];
			}
		}

		while (!q.empty()) {
			int tx = q.front().first;
			int ty = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int x = tx + mx[i];
				int y = ty + my[i];
				if (0 <= x && x < n && 0 <= y && y < m) {
					if (map[x][y] == 0 && visit_wall[x][y] == false) {
						if (virus_check[x][y] == false) {
							q.push(make_pair(x, y));
							virus_check[x][y] = true;
						}
					}
				}
			}
		}

		int tans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 0 && visit_wall[i][j] == false) {
					if (virus_check[i][j] == false) {
						tans += 1;
					}
				}
			}
		}
		if (ans == -1 || ans < tans) ans = tans;
		return;
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 0 && visit_wall[i][j] == false) {
				visit_wall[i][j] = true;
				go(cnt + 1);
				visit_wall[i][j] = false;
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) {
				v.push(make_pair(i, j));
				init_virus[i][j] = true;
			}
		}
	}

	go(0);

	cout << ans << '\n';

	return 0;
}

- bfs가 진행되는 기준은 바이러스가 이미 존재하는 곳부터다. 따라서 처음에 지도 정보를 입력 받을 때 바이러스가 있는 곳은 따로 체크해두고, 큐에도 넣어둔다. 어차피 거기서부터 바이러스가 퍼지기 시작하니까 말이다. 그게 초기화 값이 되는 거다. 

- 재귀함수를 이용해 조건에 맞는 3개의 빈 칸에 벽을 설치하면, 거기서 bfs를 돌려준다. 바이러스 방문 배열과 큐는 아까 저장해둔 값으로 초기화해서 시작한다. bfs가 끝나면 청정구역을 카운트하고 최댓값을 갱신해주면 된다.

 

* 돌 그룹 (mid) :  3개의 값을 입력 받고, 조건을 이용해 값을 동일하게 만들 수 있는지 판단하는 문제다. 쉬워 보였는데 이 파트에서는 제일 까다로웠다.

12886번: 돌 그룹

- 조건 자체에서 어떤 의미를 파악해내느냐가 가장 중요한 포인트였다. 크기가 같지 않은 두 그룹을 고르고 작은 값을 X, 큰 값을 Y라고 할 때 작은 값의 자리에 X+X를, 큰 값의 자리에 Y-X를 넣는다.

- 여기서 알 수 있는 가장 중요한 것은 이 연산을 하더라도, 3개 값의 합은 동일하다는 점이다. 예를 들어 a, b, c가 주어졌을 때 a, b를 골랐고 a < b라고 할 때, 연산을 거친 수는 2a, b-a, c다. 연산 이전 값의 합과 현재 값의 합이 a+b+c로 같다는 것을 알 수 있다. 따라서 두 가지 수만 알아도, 나머지 한 가지 수를 구할 수 있다. 이전 값의 합에서 두 수를 빼면 되기 때문이다.

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

bool check[1501][1501];
int sum;

void go(int x, int y) {
	if (check[x][y]) return;
	check[x][y] = true;
	int a[3] = { x,y,sum - x - y };
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (a[i] < a[j]) {
				int b[3] = { x, y, sum - x - y };
				b[i] += a[i];
				b[j] -= a[i];
				go(b[0], b[1]);
			}
		}
	}
}

int main()
{
	int x, y, z;
	cin >> x >> y >> z;
	sum = x + y + z;
	if (sum % 3 != 0) {
		cout << 0 << '\n';
		return 0;
	}

	go(x, y);

	if (check[sum / 3][sum / 3]) {
		cout << 1 << '\n';
	}
	else {
		cout << 0 << '\n';
	}

	return 0;
}

- 가장 먼저 3가지 수의 합이 3으로 나누어 떨어지지 않으면 3개 수를 똑같이 만들 수 없다는 것을 생각해준다. 방문기록은 제시될 수 있는 각 그룹의 최댓값이 500이므로 1500 * 1500 가지를 생각할 수 있다.

- 두 가지 수를 구하면 나머지 하나의 수를 구할 수 있다는 점을 이용해서 재귀 함수를 돌려주면서 방문기록을 해준다. 체크가 다 끝나고나면, check[sum/3][sum/3] 의 값이 true인지 확인해준다. sum/3, sum/3, sum/3 이 되는 경우가 가능한지 체크할 수 있기 때문이다.

- 두 가지 수로 재귀를 돌릴 수 있다는 점을 캐치하는 것이 조금 까다로웠던 문제였다.

-

확실히 브루트 포스에 비해서 문제 풀이가 스무스하다. 

bfs 문제에는 확실히 익숙해져 있는 것 같다.

까다로운 문제를 풀어보면서, 시간을 단축하는 연습을 많이 해야겠다.

최근에 날도 덥고, 많이 쳐진다. 그래도 꾸준히 해나가자.

스터디 카페는 시원하잖냐. 잘 하고 있다. 화이팅 하자.

정리 끝!