Machineboy空
15686 : 치킨 배달 - 조합(Combination), 브루트포스, 백트래킹 본문
https://www.acmicpc.net/problem/15686
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
문제요약
가장 효율적인 치킨 집의 개수와, 치킨 집까지의 최소 거리의 합
난이도
Gold 5
풀이 포인트
- 조합
void combi(int start, vector<int> v)
{
if (v.size() == m)
{
chickenList.push_back(v);
return;
}
for (int i = start + 1; i < chicken.size(); i++)
{
v.push_back(i);
combi(i, v);
v.pop_back();
}
return;
}
- 브루트 포스 , 백트래킹
- 치킨집을 조합하는 경우의 수 구한 뒤,
- 모든 집에서부터 치킨집까지의 거리의 합을 구하고, (브루트포스)
- 이 중 거리가 가장 최소가되는 치킨집의 조합을 알아내야함.
REVIEW
치킨집의 조합을 구하는 것이 문제의 포인트.
조합을 구하는 재귀함수를 구현하느라 시간을 다 썼다.
소스 코드 참고하지 않고 혼자 구현해보고 싶어서 어찌저찌 5개 중 3개 이하의 치킨 집의 조합을 구하는 코드까지는 구현했다.
{0,1,2}가 있다고 할 때 첫번째 요소를 뽑고 두번째요소를 뽑는다, 안뽑는다의 2가지 경우의 수,
그 다음 요소를 뽑는다, 안뽑는다의 또 2가지 경우의 수.
이런 식으로 뻗어나간다고 할 때, 매개변수 인덱스, bool값을 활용해서 어찌저찌 구현했다.
소스코드를 확인해본 결과, 비슷한 로직인 거 같긴하다.
여기에, 이제 치킨집 거리를 구해야하는데 바보처럼 최단 거리 bfs를 구해야한다고 생각하고 엄청 복잡하게 짜고 있다가,
문제를 하루지나 다시 읽어보니 그저 좌표 간 가로 세로 길이 더해주는 것이어서 수정했는데 오답.
여튼 모범답안에서 자료구조 유연하게 쓴 것들과, 인덱스 접근하는 것들 공부해두기.
조합을 for문으로만 구현해봤는데, 재귀를 맨땅에 헤딩하듯 구현해봐서 그래도 실력은 는 것 같다..
CODE
#include <bits/stdc++.h>
using namespace std;
int n, m, a[54][54], result = 987654321;
vector<vector<int>> chickenList;
vector<pair<int, int>> _home, chicken;
void combi(int start, vector<int> v)
{
if (v.size() == m)
{
chickenList.push_back(v);
return;
}
for (int i = start + 1; i < chicken.size(); i++)
{
v.push_back(i);
combi(i, v);
v.pop_back();
}
return;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> a[i][j];
if (a[i][j] == 1)
_home.push_back({i, j});
if (a[i][j] == 2)
chicken.push_back({i, j});
}
}
vector<int> v;
combi(-1, v);
for (vector<int> cList : chickenList)
{
int ret = 0;
for (pair<int, int> home : _home)
{
int _min = 987654321;
for (int ch : cList)
{
int _dist = abs(home.first - chicken[ch].first) + abs(home.second - chicken[ch].second);
_min = min(_min, _dist);
}
ret += _min;
}
result = min(result, ret);
}
cout << result << "\n";
return 0;
}
//내가 구현한 조합 코드
#include <bits/stdc++.h>
using namespace std;
int n, m,a[51][51],b[51][51];
vector<pair<int,int>> cPos;
vector<pair<int,int>> hPos;
int cnt;
void pick(int idx, bool bb){
if(bb){
b[cPos[idx].first][cPos[idx].second] = 2;
cout << cnt + 1 << "번째 조합이고, " << idx << "번 요소는 선택되었다\n";
}else{
b[cPos[idx].first][cPos[idx].second] = 0;
cout << cnt + 1 << "번째 조합이고, " << idx << "번 요소는 선택되지 않았다.\n";
}
if(idx == cPos.size()-1){
cnt++;
cout << cnt <<"번째 조합이고, 치킨집을 표시해보면\n";
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cout << b[i][j] << " ";
}
cout << '\n';
}
cout << "치킨집 리셋\n";
b[cPos[idx].first][cPos[idx].second] = 0;
return;
}
pick(idx+1, true);
pick(idx+1,false);
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n;j++){
cin >> a[i][j];
b[i][j] = a[i][j];
if(a[i][j] == 1) hPos.push_back({i,j});
if(a[i][j] == 2){cPos.push_back({i,j});
b[i][j] = 0;
}
}
}
for(int i = 0; i< cPos.size(); i++){
pick(i, true);
cout << "치킨집 리셋\n";
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (b[i][j] == 2)
b[i][j] = 0;
}
}
}
}
'Computer > Coding Test' 카테고리의 다른 글
2589 : 보물섬 - BFS (0) | 2024.02.22 |
---|---|
1068 : 트리 - DFS, 트리 (0) | 2024.02.22 |
2636 : 치즈 - DFS, BFS (1) | 2024.02.20 |
14502 : 연구소 - DFS, deep copy (0) | 2024.02.20 |
2852 : NBA 농구 - substr, prev, temp (0) | 2024.02.20 |