백준 알고리즘 기초 - bfs

순서대로 다 방문하기

최대한 스스로 풀어보려고 노력했던 파트였다.

bfs에 대한 감은 어느정도 왔지만, 아직 연습이 더 필요하다.

특히 덱 부분은 많이 새로웠다. 이번 기회에 잘 정리를 해놓자.

정리 시작!

-

* bfs : 임의의 정점에 시작해서 모든 정점을 한번씩 방문하는 것. (dfs도 마찬가지)

 - 너비를 우선으로 탐색하므로, 최단 거리를 구할 수 있는 알고리즘이다.

 - bfs로 해결할 수 있는 문제는: 최소 비용 문제, 간선의 가중치가 1, 정점과 간선의 개수가 적어야

문제 바로 풀어보자.

 

* 숨바꼭질 (mid) : 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구하는 문제다.

1697번: 숨바꼭질

- 계속 메모리 초과, 런타임 오류가 계속 떠서 애를 먹었다. 중복된 계산을 피하고, 범위 지정을 잘 해주는 게 관건이었다.

#include <iostream>
#include <queue>

using namespace std;

bool check[100001];
int dist[100001];

int main()
{
	int n, k;
	cin >> n >> k;

	queue<int> q;
	check[n] = true;
	dist[n] = 0;
	q.push(n);

	int ans = 0;
	while (!q.empty()) {
		int tmp = q.front();
		if (tmp == k) {
			ans = dist[tmp];
			break;
		}
		q.pop();

		if (tmp * 2 <= 100000) {
			if (check[tmp * 2] == false) {
				check[tmp * 2] = true;
				dist[tmp * 2] = dist[tmp] + 1;
				q.push(tmp * 2);
			}
		}

		if (tmp + 1 <= 100000) {
			if (check[tmp + 1] == false) {
				check[tmp + 1] = true;
				dist[tmp + 1] = dist[tmp] + 1;
				q.push(tmp + 1);
			}
		}

		if (tmp - 1 >= 0) {
			if (check[tmp - 1] == false) {
				check[tmp - 1] = true;
				dist[tmp - 1] = dist[tmp] + 1;
				q.push(tmp - 1);
			}
		}
	}

	cout << ans << '\n';

	return 0;
}

 - bfs의 기본만 지키면 잘 풀리는 문제였다.

 

* 숨바꼭질 4 (mid) : 이번엔 이동하는 방법까지 출력해야 한다.

13913번: 숨바꼭질 4

- 아까 위의 코드에 백트래킹할 수 있는 배열값을 추가해서 넣어주면 된다.

#include <iostream>
#include <queue>

using namespace std;

bool check[100001];
int dist[100001];
int before[100001];

int main()
{
	int n, k;
	cin >> n >> k;

	queue<int> q;
	check[n] = true;
	dist[n] = 0;
	before[n] = -1;
	q.push(n);

	int ans = 0;
	vector<int> list;

	while (!q.empty()) {
		int tmp = q.front();
		if (tmp == k) {
			ans = dist[tmp];
			list.push_back(tmp);
			while (before[tmp] != -1) {
				list.push_back(before[tmp]);
				tmp = before[tmp];
			}
			break;
		}
		q.pop();

		if (tmp * 2 <= 100000) {
			if (check[tmp * 2] == false) {
				check[tmp * 2] = true;
				dist[tmp * 2] = dist[tmp] + 1;
				before[tmp * 2] = tmp;
				q.push(tmp * 2);
			}
		}

		if (tmp + 1 <= 100000) {
			if (check[tmp + 1] == false) {
				check[tmp + 1] = true;
				dist[tmp + 1] = dist[tmp] + 1;
				before[tmp + 1] = tmp;
				q.push(tmp + 1);
			}
		}

		if (tmp - 1 >= 0) {
			if (check[tmp - 1] == false) {
				check[tmp - 1] = true;
				dist[tmp - 1] = dist[tmp] + 1;
				before[tmp - 1] = tmp;
				q.push(tmp - 1);
			}
		}
	}

	cout << ans << '\n';
	for (int i = list.size() - 1; i >= 0; i--)
		cout << list[i] << ' ';
	cout << '\n';

	return 0;
}

 

* 이모티콘 (mid) : 같은 수에서도 여러가지 값이 나올 수 있는 경우를 bfs로 계산하는 연습문제다.

14226번: 이모티콘

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

typedef struct _a {
	int now;
	int p;
	int cnt;
} str;

bool check[1001][1001];
int mint[1001];

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

	for (int i = 1; i <= 1000; i++)
		mint[i] = -1;

	queue<str> q;
	str a; 
	a.now = 1; 
	a.p = 0;
	a.cnt = 0;
	check[1][0] = true;
	mint[1] = a.cnt;
	q.push(a);

	while (!q.empty()) {
		str b = q.front();
		q.pop();
	
		str b1 = b;
		if (check[b1.now][b1.now] == false) {
			b1.p = b1.now;
			b1.cnt += 1;
			check[b1.now][b1.now] = true;
			if (mint[b1.now] == -1 || mint[b1.now] > b1.cnt) {
				mint[b1.now] = b1.cnt;
			}
			q.push(b1);
		}

		str b2 = b;
		if (b2.now + b2.p <= 1000) {
			if (check[b2.now + b2.p][b2.p] == false) {
				b2.now += b2.p;
				b2.cnt += 1;
				check[b2.now][b2.p] = true;
				if (mint[b2.now] == -1 || mint[b2.now] > b2.cnt) {
					mint[b2.now] = b2.cnt;
				}
				q.push(b2);
			}
		}

		str b3 = b;
		if (b3.now - 1 >= 0) {
			if (check[b3.now - 1][b3.p] == false) {
				b3.now -= 1;
				b3.cnt += 1;
				check[b3.now][b3.p] = true;
				if (mint[b3.now] == -1 || mint[b3.now] > b3.cnt) {
					mint[b3.now] = b3.cnt;
				}
				q.push(b3);
			}
		}
	}

	cout << mint[s] << '\n';

	return 0;
}

 - 정답 코드와 많이 다르지만, 효율성은 별로 차이가 없어서 꽤 만족스럽게 풀었다.

 - 구조체에서 now는 현재의 값을, p는 클립보드 안의 값을, cnt는 시간값을 나타낸다.

 

이번 파트에서 가장 아리까리 했던 덱 파트 문제도 풀어보자.

* 숨바꼭질 3 (mid) : 이번엔 순간이동에 소요되는 시간이 없다.

13549번: 숨바꼭질 3

- 다시 풀어보니 이렇게 편한 게 없다. 번거롭게 큐를 두개 만드는 것보다, 먼저 처리해줘야 하는 건 앞에, 나중에 처리할 건 뒤에 넣고 앞에서부터 pop 해가며 계속 계산해주면 깔끔하게 풀린다...!

- 감을 잡은 것 같은데 앞으로 애용해야겠다...

#include <iostream>
#include <deque>
#define MAX 100000
using namespace std;

bool c[100001];
int d[100001];

int main()
{
	int n, k;
	cin >> n >> k;

	d[n] = 0;
	c[n] = true;
	deque<int> q;
	q.push_front(n);

	while (!q.empty())
	{
		int x = q.front();
		q.pop_front();

		if (x * 2 <= MAX) {
			if (c[x * 2] == false) {
				c[x * 2] = true;
				d[x * 2] = d[x];
				q.push_front(x*2);
			}
		}

		if (x + 1 <= MAX) {
			if (c[x + 1] == false) {
				c[x + 1] = true;
				d[x + 1] = d[x] + 1;
				q.push_back(x+1);
			}
		}

		if (x - 1 >= 0) {
			if (c[x - 1] == false) {
				c[x - 1] = true;
				d[x - 1] = d[x] + 1;
				q.push_back(x - 1);
			}
		}
	}

	cout << d[k] << '\n';

	return 0;
}

 

* 알고스팟 (mid) : 최소 몇 개의 벽을 부수고 도착할 수 있는지 구하는 문제다.

1261번: 알고스팟

#include <iostream>
#include <cstdio>
#include <deque>

using namespace std;

int a[100][100];
int d[100][100];

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

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &a[i][j]);
			d[i][j] = -1;
		}
	}

	d[0][0] = 0;
	deque< pair<int, int> > q;
	q.push_front(make_pair(0, 0));

	while (!q.empty()) {
		int tx = q.front().first;
		int ty = q.front().second;
		q.pop_front();

		for (int i = 0; i < 4; i++) {
			int x = tx + mx[i];
			int y = ty + my[i];
			if (x >= 0 && x < n && y >= 0 && y < m) {
				if (d[x][y] == -1) {
					if (a[x][y] == 0) {
						d[x][y] = d[tx][ty];
						q.push_front(make_pair(x, y));
					}
					else {
						d[x][y] = d[tx][ty] + 1;
						q.push_back(make_pair(x, y));
					}
				}
			}
		}
	}

	cout << d[n - 1][m - 1] << '\n';

	return 0;
}

 - 어렵다고 생각했는데, 다시 풀어보니 술술 풀린다.

 - 먼저 처리해야 할 것들은 앞에, 나중에 처리할 것들은 뒤에 넣고 앞에서부터 pop 해가며 계산. 깔끔하다.

-

기분 좋게 마무리한 것 같다. 덱에 대한 이해도를 높였다. 다른 문제를 풀 때도 요긴하게 써먹어 봐야겠다.

다음 파트는 그래프 1의 마지막이자, 백준 기초 알고리즘 마지막 강의! 깔끔하게 마무리 해보자.

정리 끝!