문제

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

---

풀이

그리디 (오답)

단순히 가장 좋아 보이는 것만 계속 선택해도 최적해를 구할 수 있는 그리디로 먼저 접근해봤다.

샘터의 위치를 순회하면서 (현재 샘터의 위치 ± dist) 되는 지점에 집을 설치하면

거리의 최솟값을 구할 수 있지 않을까 생각했다.

• xi: 샘터의 위치
• dist: 샘터와 집 사이의 거리 (dist >= 1)

1. (xi ± dist) 좌표의 방문 여부를 체크한다. (음수 좌표도 가능하므로, 배열 대신 map 사용)
2. 방문하지 않은 경우, 해당 위치에 집을 설치한다.
3. 샘터와 집 사이의 거리 합을 갱신한다.
4. 집 K개를 모두 설치할 때까지 반복한다.

좌표의 범위는 -1억 ~ 1억이고, 샘터와 집은 최대 10만개이다. 따라서, 샘터와 집 사이의 거리 합은 int 범위를 넘을 수도 있으므로 long long 타입으로 선언해야 한다.

#include <iostream>
#include <string> 
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <cstring>
using namespace std;
typedef long long ll; 

const int N_MAX = 100000;
int N, K; 
int water[N_MAX];
map<int, bool> visited; 
bool isFinish = false;

void input() {
	cin >> N >> K;

	for(int i = 0; i < N; i++){
		cin >> water[i];
	}
}

void solution() {
	int dist = 1;
	ll sum = 0;

	while(!isFinish){ 
		// 샘터 위치 순회 
		for(int i = 0; i < N; i++){
			int x = water[i];

			// 샘터의 앞에 배치
			if(!visited[x - dist]) {
				visited[x - dist] = true;
				K--;
				sum += dist;
				
				if(K == 0) {
					isFinish = true;
					break;
				}
			}

			// 샘터의 뒤에 배치 
			if(!visited[x + dist]) {
				visited[x + dist] = true; 
				K--;
				sum += dist;
				
			    if(K == 0) {
					isFinish = true;
					break;
				}
			}
		}

		dist++; 
	}

	cout << sum; 
}

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

	input(); 

	solution(); 
	
	return 0;
}

그러나 오답..!! 그리디로는 최적해를 보장하지 않는 거 같다.

BFS

다른 사람의 풀이를 보니까 BFS로 풀 수 있는 문제였다. 샘터로부터의 거리를 1, 2, 3, ... 늘려가면서 집을 하나씩 설치하다가 K개를 모두 설치한 경우 거리 합의 최솟값을 리턴하면 된다.

BFS는 샘터로부터 가까운 위치를 우선 탐색하기 때문에 최솟값을 보장할 수 있다.

#include <iostream>
#include <string> 
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll; 
typedef pair<int, int> pii; 

const int N_MAX = 100000;
int N, K; 
map<int, bool> visited;
queue<int> q;
int dx[] = { 1, -1 };

void input() {
	cin >> N >> K;

	for(int i = 0; i < N; i++){
		int x; 
		cin >> x; 
		q.push(x); // 샘터의 위치 저장 
		visited[x] = true; // 방문 처리 
	}
}

ll solution() {
	int dist = 1;
	ll sum = 0;

	while(!q.empty()){
    	// 아래 for문에서 pop 연산에 의해 크기가 줄어들기 때문에 초기값 저장 
		int currentQ = q.size(); 

		for(int i = 0; i < currentQ; i++){
			int x = q.front(); 
			q.pop();
			
            // 샘터로부터 ± dist 좌표의 방문 여부 확인 
			for(int j = 0; j < 2; j++){
				int nx = x + dx[j];
				
				if(!visited[nx]){
					visited[nx] = true; 
					q.push(nx);
					
					sum += dist; // 거리합 갱신 
					K--; // 집 설치 
					
                    // 집을 모두 설치한 경우 정답 리턴 
					if(K == 0) return sum; 
				}
			}
		}

		dist++;
	}

	return sum; 
}

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

	input(); 

	cout << solution(); 
	
	return 0;
}

📌 최적화 문제를 해결하는 여러가지 방법을 정리해보자!!

• 완탐 (+ 백트래킹)
• 그리디
• DP (규칙성을 바탕으로 점화식 세우기)
• 이분 탐색 (파라메트릭 서치)
• BFS (최단 경로, 최솟값 보장)