[백준] 18513번 - 샘터 (C++) 문제 및 풀이

문제) 백준 - BFS - 샘터

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

18513번: 샘터

 

BFS를 통해서 각 샘터를 기준으로 지을 수 있는 집의 최소 불행도를 구한다. 주언진 샘터의 좌표를 Queue에 push 하여 매번 Queue size마다 K개 집에 대하여 거리를 더해준다. 

 

C++ 소스 코드)

	while (!q.empty()) {
	if (tt == K) break;
	int q_size = q.size();
	dis++;
	for (int j = 0; j < q_size; ++j) {
	int now = q.front(); q.pop();
	if (0 <= now - 1 && !dist[now - 1]) {
	dist[now - 1] = true;
	tt++;
	ans += dis;
	if (tt == K) break;
	q.push(now - 1);
	}
	if (now + 1 < MAX && !dist[now + 1]) {
	dist[now + 1] = true;
	tt++;
	ans += dis;
	if (tt == K) break;
	q.push(now + 1);
	}
	}
	}

view raw 18513.cpp hosted with ❤ by GitHub

 

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2015000~19999/18513_%EC%83%98%ED%84%B0.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions