[C/C++ 백준 15686번] 치킨 배달 (Gold 5)

www.acmicpc.net/problem/15686

15686번: 치킨 배달

굉장히 복잡한 문제. 그래도 풀 수 있을거 같아 꽤 많은 시간을 쏟아 코딩해보았다.

문제의 내용에 들어가는 함수들은,

 

1. 가장 가까운 거리의 치킨집을 찾아 거리를 리턴하는 함수(BFS활용),

2. 1을 이용해서 해당 경우에서 치킨 거리를 계산하는 함수,

3. 2를 이용해서 특정한 케이스(몇 개를 골라 폐업시킨 경우)에서 치킨 거리를 계산 한뒤 ans과 비교해 최소값을 찾는 함수.

 

이렇게 만들어 풀었지만,,

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int N, M, graph[51][51], ans=999999;
int xmove[4]={-1,0,1,0};
int ymove[4]={0,1,0,-1};
vector <pair<int, int>> chick;
//폐업시킬치킨집 chick.size()-M개 고르기
//각 고른거마다 치킨 거리의 최솟값 계산하기
int dis(int x, int y){
	bool visit[N][N];
	int depth[N][N];
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++)
			visit[i][j] = false;
	visit[x][y] = true;
	queue <pair<int, int>> q;
	q.push({x, y});
	depth[x][y] = 0;
	while(!q.empty()){
		pair <int, int> p = make_pair(q.front().first, q.front().second);
		q.pop();
		for(int i=0; i<4; i++){
			if((p.first+xmove[i] < N && p.second+ymove[i] < N) &&
			(p.first+xmove[i] >=0 && p.second+ymove[i] >=0 )){
			if(visit[p.first+xmove[i]][p.second+ymove[i]]==false){
				visit[p.first+xmove[i]][p.second+ymove[i]]=true;
				depth[p.first+xmove[i]][p.second+ymove[i]]=(depth[p.first][p.second]+1);
				q.push({p.first+xmove[i], p.second+ymove[i]});
				if(graph[p.first+xmove[i]][p.second+ymove[i]]==2){
					return depth[p.first+xmove[i]][p.second+ymove[i]];
				}
			}	
			}
			
		}
	}
}
int func(){
	int cnt = 0;
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			if(graph[i][j]==1){
				cnt += dis(i, j);
			}
		}
	}
	return cnt;
}
void select(int start, int cnt, vector <pair<int, int>> v){
	if(start == chick.size() && cnt<chick.size()-M){
		return ;
	}//모두 돌았는데, 다 못고른 경우 
	if(cnt == chick.size()-M){
		for(int i=0; i<v.size(); i++)
			graph[v[i].first][v[i].second] = 0;
		ans = min(ans, func()); 
		for(int i=0; i<v.size(); i++)
			graph[v[i].first][v[i].second] = 2;
	}
	//모두 선택했을 경우
	else{
		select(start+1, cnt, v);//선택 안함 
		v.push_back({chick[start].first, chick[start].second});
		select(start+1, cnt+1, v);//선택 함 
	}//아직 모두 선택 x 
} 
int main(void){
	scanf("%d %d", &N, &M);
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			scanf("%d", &graph[i][j]);
			if(graph[i][j]==2){
				chick.push_back({i,j});
			}
		}
	}
	vector <pair<int, int>> v;
	select(0,0,v);
	printf("%d", ans);
}

 

시간 초과라는 결과가 나왔다. 후에 바로 질문 검색을 보니, BFS로 해결했던 가장 가까운 거리의 치킨집을 찾는게 O(1)로도 가능하다고 한다.

 

그래서 든 생각이, 현재 남아있는 치킨집을 저장하는 벡터를 하나 더 만들어 해당 집들과의 거리를 비교하는 방법이다.

 

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, M, graph[51][51], ans=999999;
int xmove[4]={-1,0,1,0};
int ymove[4]={0,1,0,-1};
vector <pair<int, int>> chick;
vector <pair<int, int>> restchick;
//폐업시킬치킨집 chick.size()-M개 고르기
//각 고른거마다 치킨 거리의 최솟값 계산하기
int abs(int x, int y){
	if(x>y)
		return x-y;
	return y-x;
}
int dis(int x, int y, vector <pair<int, int>> w){
	int ans = 999999;
	for(int i=0; i<w.size(); i++){
		ans = min(ans, abs(w[i].first, x) + abs(w[i].second, y));
	}
	return ans;
}
int func(vector <pair<int, int>> w){
	int cnt = 0;
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			if(graph[i][j]==1){
				cnt += dis(i, j, w);
			}
		}
	}
	return cnt;
}
void select(int start, int cnt, vector <pair<int, int>> v, vector <pair<int, int>> w){
	if(start == chick.size() && cnt<chick.size()-M){
		return ;
	}//모두 돌았는데, 다 못고른 경우 
	if(cnt == chick.size()-M){
		for(int i=0; i<v.size(); i++)
			graph[v[i].first][v[i].second] = 0;
		ans = min(ans, func(w)); 
		for(int i=0; i<v.size(); i++)
			graph[v[i].first][v[i].second] = 2;
	}
	//모두 선택했을 경우
	else{
		select(start+1, cnt, v, w);//선택 안함 
		v.push_back({chick[start].first, chick[start].second});
		for(int i=0; i<w.size(); i++){
			if(w[i].first==chick[start].first &&
			w[i].second==chick[start].second)
				w.erase(w.begin()+i);
		}
		select(start+1, cnt+1, v, w);//선택 함 
	}//아직 모두 선택 x 
} 
int main(void){
	scanf("%d %d", &N, &M);
	vector <pair<int, int>> v;
	vector <pair<int, int>> w;
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			scanf("%d", &graph[i][j]);
			if(graph[i][j]==2){
				chick.push_back({i,j});
				w.push_back({i,j});
			}
		}
	}
	select(0,0,v,w);
	printf("%d", ans);
}