Week4 - BFS

📝 문제 목록

• [🥈1] 1697 - 숨바꼭질
• [🥇5] 5014 - 스타트링크
• [🥇5] 14226 - 이모티콘

개인적으로 공부한 내용을 작성한 것으로 틀린 부분이 있을 수 있습니다
혹 틀린 부분이 있다면 지적해주시면 감사하겠습니다🙏

1. 숨바꼭질

그리디를 떠올릴 수도 있지만 그리디를 사용하는 것은 좋은 방법이 아님을 금방 알 수 있다. 예를 들어 5에서 12로 간다고 했을 때, 가장 빠르게 가는 경로는 5->6->12 이지만
그리디를 사용하면 5->10->11->12의 경로로 가게 될 것이다.
이 문제처럼 최단 경로를 찾을 때 주로 BFS를 사용하는데, 큐를 사용해서 반복문 한 턴에 갈 수 있는 위치들을 큐에 넣고 각 위치의 카운트를 현재 카운트+1로 저장해가는 방식이다.
일단 큐가 빌 때까지 작업을 반복하는데 도중에 정답이 나오면 반복문을 종료한다.
이때 주의해야 할 점이 있다. 다음을 고려하지 않으면 메모리 초과나 런타임 에러가 뜰 수 있다.

• 방문 처리: 방문 처리를 해주지 않으면 방문했던 위치가 계속해서 큐에 push되므로 큐로 인한 메모리 초과가 발생.
• 방문 범위 제한: 방문 배열의 인덱스를 벗어난 경우 런타임 에러 발생.

따라서 방문 처리를 위해 bool형 배열을 만들어 주고 배열의 크기 및 방문 제한 지점은 문제에서 위치의 최대값인 100000을 넘지 않도록 했다.
(어떤 위치 n까지 가는 최단경로에 n을 초과하는 위치가 들어갈 수도 있기는 하지만 그런 경우는 홀수일때나 존재하고(ex: 5->10->9) 홀수가 아니라면 n/2 지점에서 2배를 한 것보다 n을 초과한 위치에서 -1로 이동하는 게 더 빠를 수는 없을 것이다)

시간복잡도로 따져본다면 만약 이렇게 방문처리를 해주지 않고 실행했을 때는 반복문 한 턴당 경로가 3가지이므로 시간복잡도가 O(3^n)이 될 것이다.
하지만 방문처리할 경우에는 같은 정점을 두 번 이상 방문하지 않으므로 시간복잡도가 크게 줄어든다.
여기서는 간선 정보를 인접행렬로 저장했으므로 V개의 정점과 다른 모든 정점에 대해 연결되었는지 체크하는 시간까지 총 O(V^2)의 시간복잡도가 걸린다.
인접 리스트 방식을 사용할 경우 모든 정점을 방문하는 시간+모든 간선을 방문하는 시간만큼만 걸린다. 즉 시간복잡도는 O(V+E)이 된다. (V: 정점개수, E: 간선개수) BFS의 방문 흐름을 그래프로 그려보면 이해하기 쉽다.
(참고: https://www.acmicpc.net/board/view/47137)

큐에 들어갈 자료형은 pair<int, int>를 사용했다. 문제 풀 당시에는 생각이 안 나서 다른 자료형을 사용했는데 스터디에서 코드리뷰를 듣고 고쳤다.
실은 여러번 풀어봤던 유형인데도 이번에 풀었을 때 기본적인 부분들에서 실수를 범했다는 것에 대해, 그리고 기억은 잘 안 나지만 분명 이게 처음 한 실수는 아니었을 것이라는 생각에 좀 반성했다.
너무 급하게 풀려고 해서 그랬을까? 스피디하게 푸는 것도 중요하지만 그보다 우선 작성한 알고리즘에 빈틈이 없는지 좀더 꼼꼼하게 체크하며 풀도록 하자. 발생할 수 있는 여러가지 경우를 생각해가면서…

그리고 아래 코드에서 방문 체크를 push할때가 아니라 pop하는 시점에서 해줬는데 오답은 아니지만 역시 push할때(=범위체크할때) 같이 체크하는 게 좋을 것 같다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, k, cur_pos;
	int cur_cnt = 0;
	vector<bool> check;
	queue<pair<int, int>> q;
	cin >> n >> k;

	check.assign(100001, false);
	q.push({ n, cur_cnt });

	while (!q.empty()) {
		cur_pos = q.front().first;
		cur_cnt = q.front().second;
		q.pop();

		if (cur_pos == k) break;

		if (!check[cur_pos]) {
			check[cur_pos] = true;

			if (cur_pos - 1 >= 0) q.push({ cur_pos - 1, cur_cnt + 1 });
			if (cur_pos + 1 <= 100000) q.push({ cur_pos + 1, cur_cnt + 1 });
			if (cur_pos * 2 <= 100000) q.push({ cur_pos * 2, cur_cnt + 1 });
		}
	}

	cout << cur_cnt;
}

2. 스타트링크

위 문제와 비슷한 문제이나 이 문제는 주어진 이동거리에 따라서 정답이 나오지 않을 수도 있는 문제이다. 그럴 경우 “use the stairs”를 출력해야 한다.
생각해보니 카운트 데이터가 초기값(0)이 아니라면 방문했다는 의미가 되므로 따로 방문 체크 배열을 만들 필요가 없을 것 같아 카운트 값으로 체크하도록 했다. (단 시작점은 0이어야 하므로 시작점은 제외)
따라서 큐에 push되는 조건으로는, 현재위치+U(위로 이동)와 현재위치-D(아래로 이동)에 대하여

1
2
3

① 이동 후의 위치가 S(시작점)가 아니고
② 방문하지 않았고
③ 층수제한을 넘지 않을 때(1~F일 때)

각각 push하도록 했다.
그리고 정답이 나오지 않았을 수도 있으므로 반복문이 종료된 후 현재 위치가 G(목표지점)가 아니라면 “use the stairs”를 출력하게 했다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int f, s, g, u, d, cur;
	vector<int> cnt;
	queue<int> q;
	cin >> f >> s >> g >> u >> d;

	cnt.assign(f + 1, 0);
	cur = s;
	q.push(s);

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

		if (cur == g) break;

		int up = cur + u;
		int down = cur - d;
		if (up != s && up <= f && cnt[up] == 0) {
			cnt[up] = cnt[cur] + 1;
			q.push(up);
		}
		if (down != s && down > 0 && cnt[down] == 0) {
			cnt[down] = cnt[cur] + 1;
			q.push(down);
		}
	}

	if (cur == g) cout << cnt[g];
	else cout << "use the stairs";
}

3. 이모티콘

이 문제도 위치라는 표현이 이모티콘 개수로 바뀌었을 뿐 위 두 문제와 비슷한 유형이지만, 여기서는 그 변화량이 가변적이다. 현재 클립보드에 몇 개의 이모티콘이 저장되어 있냐에 따라 늘어나는 개수가 달라진다.
또한 클립보드를 복사하는 행위도 카운트에 포함된다.

사실 나는 가장 먼저 DP방식을 떠올렸다. 클립보드에서 몇개짜리를 붙여넣었느냐에 따라 같은 결과더라도 연산 횟수가 다른 경우가 있으므로, 다음과 같이 생각했다.

1
2
3

반복문을 통해 현재 입력된 이모티콘 개수 로 만들 수 있는 모든 이모티콘 개수의 경우에 대한 카운트를 구한다.
(현재 입력된 이모티콘의 카운트값 + 복사1번 + 붙여넣기 n번)
이때 어떤 개수에 대해 카운트를 처음 구했거나 이전에 구한 카운트 값보다 작을 때만 카운트값을 갱신한다.

이 이후 이모티콘을 하나 삭제했을 때의 카운트값도 구해서 위 동일 조건으로 비교해 갱신했다.
그런데 이건 말했듯이 DP라서 BFS로 풀려면 다른 방법으로 접근해야 하는데, 아무리 생각해도 저 방법 말고는 떠오르지 않아서 저기다 BFS를 만든답시고 뭔가 괴상한 코드를 만들어내고 말았다… 통과는 했지만 큐에 넣는다고 BFS가 되는게 아닌것을… 암튼 그래서 스터디 이후 제대로 된 BFS 방식으로 다시 코드를 짜 보았다. 이미 스터디와 인터넷에서 다른 사람들의 풀이를 봐버렸기 때문에 아래는 직접 생각해낸 내용은 아니고 그냥 복습 겸 흐름을 정리해봤다.

일단 위에서 말했던 것처럼 n개의 이모티콘을 만들기 위해 사용한 클립보드 경로는 여러가지가 있을 수 있고, 각각의 경로에 대한 연산 횟수도 다를 수 있다.
그러므로 ‘n개의 이모티콘을 만들기 위해 선택한 어떤 경로’에 대한 연산 횟수를 경로별로 알아야 한다.

한 번의 연산에서 선택할 수 있는 경로는 3가지이다.

1
2
3

① 화면에 있는 이모티콘을 클립보드로 복사
② 클립보드에 있는 이모티콘을 화면에 붙여넣기
③ 화면에 있는 이모티콘을 하나 삭제

이를 화면에서의 이모티콘 개수(sn)와 클립보드에서의 이모티콘 개수(cn) 변화로 나타내면 아래와 같다.

1
2
3

① sn,cn -> sn,sn
② sn,cn -> sn+cn,cn
③ sn,cn -> sn-1,cn

즉 이전 문제들에서는 위치만 변경되었지만 이 문제에서는 화면과 클립보드 두 가지가 변경된다. 따라서 이를 2차원 배열로 만들어서 카운트한다는 아이디어를 떠올린다면 문제를 쉽게 해결할 수 있다.
큐에 들어갈 자료형은 개인적으로 sn,cn을 묶고 cnt를 따로 둔 형태가 마음에 들어서 이중 pair를 사용했다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include<iostream>
#include<queue>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int s;
	int cnt = 0;
	bool check[1001][1001] = { false };
	queue<pair<pair<int, int>, int>> q;
	cin >> s;

	check[1][0] = true;
	q.push({ { 1,0 }, 0 });

	while (!q.empty()) {
		int sn = q.front().first.first;
		int cn = q.front().first.second;
		cnt = q.front().second;

		if (sn == s) break;

		q.pop();

		if (sn > 0 && sn < 1001) {
			// 화면의 내용을 클립보드에 복사 (sn,cn -> sn,sn)
			if (!check[sn][sn]) {
				check[sn][sn] = true;
				q.push({ { sn, sn }, cnt + 1 });
			}

			// 클립보드의 내용을 화면에 붙여넣기 (sn,cn -> sn+cn,cn)
			if (sn + cn < 1001 && cn > 0 && !check[sn + cn][cn]) {
				check[sn + cn][cn] = true;
				q.push({ { sn + cn, cn }, cnt + 1 });
			}

			// 화면의 이모티콘을 1개 삭제 (sn,cn -> sn-1,cn)
			if (!check[sn - 1][cn]) {
				check[sn - 1][cn] = true;
				q.push({ { sn - 1, cn }, cnt + 1 });
			}
		}
	}

	cout << cnt;
}