[G4] 백준 18513번 샘터 C++ 너비 우선 탐색, 해시셋

리뷰

 

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

K채의 집을 지을 때, 가능하면 샘터의 주변에 집들을 지어서 K채의 모든 집에 대한 불행도의 합이 최소가 되도록 짓는 문제

 

 

전역 변수

• n : 샘터의 개수를 저장할 변수
• k : 지어야 할 집의 개수를 저장할 변수
• ans : 정답을 출력하기 위한 변수
• dx : 2방향 탐색을 위한 방향 배열
• PD : 현재 위치와 가장 가까운 샘터로 부터의 거리를 정의할 구조체
• q : 너비 우선 탐색에서 사용할 PD타입의 큐
• v : 좌표 기반 방문 여부를 체크하기 위한 해시셋

 

함수

1. bfs

void bfs() {
	while (!q.empty()) {
		PD pd = q.front(); q.pop();
		int p = pd.p, d = pd.d;

		for (int i = 0; i < 2; ++i) {
			int np = p + dx[i], nd = d + 1;
			if (!v.count(np)) {
				v.insert(np);
				ans += nd;
				q.push({ np, nd });
				if (!--k) return;
			}
		}
	}
}

 

샘터랑 가장 가까운 위치에 집을 지을 때 모든 집에서 샘터까지 거리의 최소값을 구하기 위한 함수

 

 

문제풀이

1. n, k값을 입력 받고, n개의 샘터 좌푤르 변수 x에 입력 받고, 방문처리 후 큐에 push해준다. 이때 좌표는 x, 누적 거리는 0이다.
2. bfs함수를 호출해 주어 q가 빌때까지 while루프를 순회하고 매 루프마다 요소를 한개씩 꺼내어 준다.
3. 변수 p, d에 현재 요소의 위치와 가장 가까운 샘터와의 거리를 파싱하여 저장해 준다.
4. 2방향 탐색을 통해 이동할 위치 np가 방문처리 되어있지 않다면 이동을 진행해 준다.
5. 이동 후엔 방문처리 후 ans에 누적 거리를 1만큼 증가시킨 값을 더해준다.
6. q에 이동한 위치와 누적 거리를 push해주고, k를 감소시킨다, 만약 k가 0이 되었다면 리턴해 준다.

 

트러블 슈팅

1. 문제의 조건에 (-100,000,000 ≤ 샘터의 위치 ≤ 100,000,000)라고 되어 있어 집도 해당 범위 내에 지어야 한다고 생각했다.
2. 따라서 샘터가 -1억 혹은 1억에 있을 경우 ans가 int범위를 넘길 가능성이 있어 ans를 long long으로 변경하였다.
3. 하지만 int범위 오버플로 문제는 아니였고, 그냥 샘터의 위치가 -1억~1억일 뿐 집의 위치는 해당 범위와 상관 없었다.
4. BFS를 진행할 때 범위 체크 조건을 제거하고, 방문 여부만 체크하니 AC를 받았다.

 

참고 사항

1. 집의 위치가 음수 및 1억까지 나올 수 있으므로 일반 배열이 아닌 해시를 사용해 방문 처리를 진행해 주었다.

 

정답 코드

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

int n, k;
long long ans;
int dx[] = { -1, 1 };
struct PD {
	int p, d;
};
queue<PD> q;
unordered_set<int> v;

void bfs() {
	while (!q.empty()) {
		PD pd = q.front(); q.pop();
		int p = pd.p, d = pd.d;

		for (int i = 0; i < 2; ++i) {
			int np = p + dx[i], nd = d + 1;
			if (!v.count(np)) {
				v.insert(np);
				ans += nd;
				q.push({ np, nd });
				if (!--k) return;
			}
		}
	}
}

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

	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		int x; cin >> x;
		v.insert(x);
		q.push({ x, 0 });
	}

	bfs();
	cout << ans;
}