백준 15686번 - 치킨 배달 (2회 차)

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

15686번: 치킨 배달

풀이 과정

 치킨집들 중 m개를 뽑고, 해당 경우의 수 일 때 도시의 치킨 거리를 구한다. 이때 최소 치킨 거리를 구하는 문제이다. 치킨 거리는 집과 치킨집의 최단 거리를 말한다.

 

느낀 점

 역시 머릿 속에 로직이 있으니 첫 구현은 간단했다. 하지만 2번의 막힘이 있었다.

 

 첫 번째는 조합을 구현할 때 combi() 함수의 인자를 i가 아닌 idx로 주어서 같은 값이 여러번 중복되어 나타났다. 처음 풀 때도 같은 실수를 한 걸 생각하면 조합 구현이 아직 미숙한 것 같다. 그 때와 같이 조합값을 디버깅하며 검사하다가 발견했다.

 

 두 번째는 문제에서 최댓값을 잘못 파악했다. n의 최댓값은 50이고 m의 최댓값은 13이다. 하지만 n의 최댓값을 13으로 보고, MAX를 13으로 설정해줘서 오답을 받았다. 기본적인 실수임에도 문제를 다시 읽지는 않아서 파악하는데 오래 걸렸다. 이전에 소스 코드를 보고 비교하던 중, 이전 코드에는 NMAX라는 값을 따로 할당해준 것을 보고 알아차렸다. 디버깅 값이 모두 맞고 어디서 잘못된 것인지 모를때는 문제의 조건을 잘못 파악하지는 않았는지 생각하며 문제를 다시 보자. 

 

#include<bits/stdc++.h>
using namespace std;

const int MAX = 50;
int n, m, cnt, ret, min_dis = 2098765432;
int mp[MAX][MAX], visited[MAX][MAX], dis[MAX][MAX];
int my[4] = { 1, 0, -1, 0 }, mx[4] = { 0, 1, 0, -1 };
vector<pair<int, int>> chicken, home, com;

//BFS로 탐색하며 visited에 거리 저장
void BFS(int y, int x) {
	queue<pair<int, int>> q;
	visited[y][x] = 1;
	q.push({ y, x });
	while (q.size()) {
		int nowy = q.front().first;
		int nowx = q.front().second;
		q.pop();
		for (int d = 0; d < 4; d++) {
			int ny = my[d] + nowy;
			int nx = mx[d] + nowx;
			if (ny < 0 || ny >= n || nx < 0 || nx >= n || visited[ny][nx]) continue;
			visited[ny][nx] = visited[nowy][nowx] + 1;
			q.push({ ny, nx });
		}
	}
	return;
}

//경우의 수를 구하고, 해당 경우에서 최소 치킨 거리를 갱신
void combi(int idx) {
	if (com.size() == m) {
		//경우의 수 생성, com의 치킨집 좌표 마다 BFS 실행
		int sum = 0;
		fill(&dis[0][0], &dis[0][0] + MAX * MAX, 2098765432);
		for (int i = 0; i < com.size(); i++) {
			fill(&visited[0][0], &visited[0][0] + MAX * MAX, 0);
			BFS(com[i].first, com[i].second);
			//visited 와 dis min()을 통해 갱신
			for (int j = 0; j < home.size(); j++) {
				int hy = home[j].first;
				int hx = home[j].second;
				dis[hy][hx] = min(dis[hy][hx], visited[hy][hx] - 1);
			}
		}

		//치킨 거리 합 구하고 최소값 갱신
		for (int i = 0; i < home.size(); i ++) {
			sum += dis[home[i].first][home[i].second];
		}
		min_dis = min(min_dis, sum);

		return;
	}

	for (int i = idx + 1; i < chicken.size(); i++) {
		com.push_back(chicken[i]);
		combi(i);
		com.pop_back();
	}

	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//입력
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++){
			cin >> mp[i][j];
			if (mp[i][j] == 2) chicken.push_back({ i, j });
			if (mp[i][j] == 1) home.push_back({i, j});
		}
	}

	combi(-1);

	cout << min_dis;

	return 0;
}