백준 15686번 치킨 배달 풀이

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

BFS + 조합 완전탐색

 

치킨집에서 집으로 배달을 한다고 문제 이름 그대로 받아들였으면 빨리 풀었을 것 같다

처음에 손님들이 치킨집에 가서 치킨먹는 그림을 생각하고 풀었다가 실패했다.

내가 멍청한거랑 도대체 무슨 상관일까 싶지만 ㅋㅋㅋ

 

최소여야하는건 집에서 치킨집까지의 치킨 거리의 합이니 주어진 m개의 치킨집은 모두 써야 한다.

그리고 치킨집의 개수 중에서 m개를 뽑아 m개의 치킨집으로 만들 수 있는 모든 경우를 검사했다.

문제에서 대놓고 조합으로 모든 경우를 구하라고 써놓은것같다..

 

몇달 전 이 문제를 처음 풀었을 때는 모든 집의 입장에서 치킨집까지의 거리를 구하려고 시도했었지만 시간초과가 났다.

집의 입장에서 모든 조합된 치킨집들과의 거리를 구해도 정답은 나오겠지만 문제는 집의 개수만큼 BFS를 돌려야 된다는 부분이다. 집이 100개라면 100개의 집에서 모두 각각 처음으로 치킨집을 만날때까지... 그리고 그걸 치킨집의 조합이 만들어내는 경우의 수만큼 BFS를 돌려야한다.

 

조합은 역시 c++ algorithm 헤더의 next_permutation을 사용했고 항상 생각하는건데 참 순수하고 멍청한(?) 방법인 것 같다. 뽑을것과 안뽑을것으로 0과 1로 구분해놓고 순열로 섞어서 뽑을 1님 자리 인덱스 가져오기 ㅎㅎ.. next_permutation은 꼭 뒤가 큰 형태로 정렬해놓고 사용하는 걸 잊지 말아야 한다. 이걸 까먹고 쓰면 오류 잡는데에 답도 없다

 

치킨집이 최대 13개라서 만만하게 보였지만 생각해보니 대충 13개중에 6개를 뽑는다고 생각해도 1716개의 경우가 나온다. 100개의 집이 모두 치킨집을 찾을 때 까지 각각 BFS를 하는데 그게 1716번... 그리고 visit 처리도 각 집의 입장마다 다르기 때문에 꼼짝없이 집집마다 초기화한 visit로 새로 시작해야 하는데 너무 오래걸린다.

 

반대로 치킨집의 입장에서 집을 탐색한다면 많은 시간을 줄일 수 있다.

가서 먹지말고 똑똑하게 배달을 시키란 말이야...!!!!

 

같은 경우로 100개의 집, 6개의 치킨집, 1716개의 경우라고 생각했을 때

집의 개수를 미리 알고 모든 집을 찾을 때까지 치킨집에서 출발해 BFS를 돌린다면 같은 1716번이지만 출발점은 6개로 많이 줄어든다. 그리고 치킨집들에서 동시에 BFS에 참여할 수 있기 때문에 한 조합을 검사할 때 visit를 공유할 수 있다. 다른 치킨집에서 이미 검사했다면 나보다 가까운애를 두고 내가 또 주제넘게 검사할 필요는 없으니까

  

Queue를 사용하면 어차피 First In First Out이니까 초기 Push를 모든 치킨집들의 위치로 해두면 그 이후에는 일반적인 BFS와 아주 똑같다. 출발점에서부터 지나온 거리가 같은 지점들은 그 출발점이 어디였든 항상 연속해서 검사될 것이다. 

 

소스 코드

 

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

using namespace std;
int n, m, house = 0, chicken = 0, mi = 99999999;
int input[51][51];

vector<pair<int, int>> chicken_pos;


int dxy[4][2] = { {-1,0}, {0,1}, {1,0}, {0,-1} };
void bfs(vector<int> now_c) {
	bool visit[51][51] = { 0, };
	queue<vector<int>> q;
	int tmp[51][51];
	int t_house = house;
	int ret = 0;
	//:copy(&input[0][0], &input[0][0] + 51*51, &tmp[0][0]);

	for (int i = 0; i < now_c.size(); i++) {
		q.push({ chicken_pos[now_c[i]].first, chicken_pos[now_c[i]].second, 0 });
		visit[chicken_pos[now_c[i]].first][chicken_pos[now_c[i]].second] = true;
	} //모든 치킨집 push

	while (!q.empty()) {
		int now_x = q.front()[0], now_y = q.front()[1], now_cnt = q.front()[2];
		q.pop();
		//cout << "now_x: " << now_x << "now_y: " << now_y << "now_cnt: " << now_cnt << endl;
		if (input[now_x][now_y] == 1) {
			t_house--;
			//cout << " here x y: " << now_x << ", " << now_y << endl;
			ret += now_cnt;
		}
		if (!t_house) break;
		for (int i = 0; i < 4; i++) {
			int next_x = now_x + dxy[i][0];
			int next_y = now_y + dxy[i][1];
			if (next_x < 0 || next_x >= n || next_y < 0 || next_y >= n ) continue;
			if (visit[next_x][next_y]) continue;
			visit[next_x][next_y] = true;
			q.push({ next_x, next_y, now_cnt + 1 });
		}
	}
	mi = min(mi, ret);
}


int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> input[i][j];
			if (input[i][j] == 1) house++;
			else if (input[i][j] == 2) chicken_pos.push_back({ i,j });
		}
	}


	vector<int> t;
	for (int k = 0; k < chicken_pos.size() - m; k++) {
		t.push_back(0);
	}
	for (int k = 0; k < m; k++) {
		t.push_back(1);
	}

	do {
		vector<int> now_c;
		for (int k = 0; k < chicken_pos.size(); k++) {
			if (t[k]) now_c.push_back(k);
		}
		bfs(now_c);
	} while (next_permutation(t.begin(), t.end()));

	cout << mi;
	return 0;
}

 

 

문제를 자주 풀다 보니 큐나 visit같이 계속 쓰는 자료들을 무조건 전역 변수로 두고 시작하는 습관이 생겼는데 경우에 따라 지역변수로 초기화하고 쓰는게 더 편할 때가 많은 것 같다. 재사용하는데 괜히 전역변수로 뒀다가 초기화를 까먹어서 이유를 찾지못해 시간을 버리는 바보같은 짓을 많이 하니까...

 

보자마자 집의 입장에서 BFS를 돌리려고 한 것이나, 죄다 전역변수로 두려하는 습관이나 모두 생각없이 문제 푸는 갯수만 늘리다보니 생기는 못된 버릇인 것 같다. 충분히 생각해보고 코드로 구현 시작하는 습관을 들여야겠다.