💬문제 정리 및 아이디어
- 집을 기준으로 가장 가까운 치킨집까지 거리는 치킨 거리이고, 도시의 치킨거리는 모든 집의 치킨 거리의 합이다
- 도시에 있는 치킨집 중 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시킬 때, 어떻게 고르면 도시의 치킨 거리가 가장 작게 되는지 구해야 한다
- 치킨집 중 최대 M개를 고르는 부분은 DFS를 이용한 조합으로 구한다
- 폐업시키지 않을 치킨집을 골랐을 때, 모든 집에 대해 가장 가까운 치킨집까지의 거리를 구해 더해준다
Solution 1 (메모리 초과, 시간 초과)
처음 데이터를 입력받을 때, 집과 치킨집의 좌표를
vector<pair <int, int>> chick, home에 입력받는다치킨집을 최대
M개를 고른다고 했으므로,1개, 2개, 3개... m개골랐을 때 매번 탐색을 해주었다모든 home에 대해 BFS함수를 호출하여 해당 위치에서 가장 가까운 선택된 치킨집까지의 거리를 구하고, 더해준다
👩💻
1. input datavector<pair <int, int>> chick; vector<pair<int, int>> home;void input() { cin >> N >> M; city = vector<vector<int>>(N, vector<int>(N)); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> city[i][j]; if (city[i][j] == HOME) home.push_back({ i,j }); if (city[i][j] == CHICKEN) chick.push_back({ i,j }); } } }
👩💻
2. 최대 M개의 치킨집 고르기- DFS 조합
dfs함수의 종료 조건은m개 초과의 치킨집이 골라졌을 때- 모든 집
(home.size()개)에서 선택된 치킨집(cnt개)까지의 거리를 탐색하는 조건은 선택된 치킨집이1개이상m개이하일 때void dfs(int cnt, int start) { if (cnt > M) return; if (cnt>0 && cnt<= M) { int chickDist=0; for (int i = 0; i < home.size(); i++) chickDist+=checkDist(i); ret = min(ret, chickDist); } for (int i = start; i < chick.size(); i++) { selected[i] = true; dfs(cnt + 1, start + 1); selected[i] = false; } }
bool selected[i]는i번 째chick이 선택되었는가 즉, 폐점하지 않기로 했는가 이다.
👩💻 3.
checkSelected(int y, int x)
bfs함수에서 해당 집 위치에서 가장 가까운 치킨집을 탐색할 때, 치킨집이 나오면 이 치킨집이 선택된 치킨집인지 아닌지 알아보아야 한다bool checkSelected(int y, int x) { for (int i = 0; i < chick.size(); i++) { int r = chick[i].first; int c = chick[i].second; if (y == r && x == c) { if (selected[i]) return true; else return false; } } }
👩💻
4. BFS- checkDist(int idx)
idx번 째 집에서 가장 가까운 치킨 집을 찾는다- 가장 가까운 선택된 치킨집이 나왔을 때, 집에서 치킨집까지의 거리를
return해준다int checkDist(int idx) { queue<pair<int, int>> q; int hy = home[idx].first; int hx = home[idx].second; q.push({ hy, hx }); while (!q.empty()) { int y = q.front().first; int x = q.front().second; q.pop(); for (int dir = 0; dir < 4; dir++) { int ny = y + dy[dir]; int nx = x + dx[dir]; if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue; if (city[ny][nx] == CHICKEN && checkSelected(ny, nx)) { return (abs(ny - hy) + abs(nx - hx)); } q.push({ ny, nx }); } } }
전체코드
#include <iostream> #include <vector> #include <queue> #include <cmath> using namespace std; enum {EMPTY, HOME, CHICKEN}; vector<pair <int, int>> chick; vector<pair<int, int>> home; vector<vector<int>> city; bool selected[11]; int ret = 0x7fffffff; int N, M; int dy[] = { 0,0,1,-1 }; int dx[] = { 1,-1,0,0 }; bool checkSelected(int y, int x) { for (int i = 0; i < chick.size(); i++) { int r = chick[i].first; int c = chick[i].second; if (y == r && x == c) { if (selected[i]) return true; else return false; } } } int checkDist(int idx) { queue<pair<int, int>> q; int hy = home[idx].first; int hx = home[idx].second; q.push({ hy, hx }); while (!q.empty()) { int y = q.front().first; int x = q.front().second; q.pop(); for (int dir = 0; dir < 4; dir++) { int ny = y + dy[dir]; int nx = x + dx[dir]; if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue; if (city[ny][nx] == CHICKEN && checkSelected(ny, nx)) { return (abs(ny - hy) + abs(nx - hx)); } q.push({ ny, nx }); } } } void dfs(int cnt, int start) { if (cnt > M) return; if (cnt>0 && cnt<= M) { int chickDist=0; for (int i = 0; i < home.size(); i++) chickDist+=checkDist(i); ret = min(ret, chickDist); } for (int i = start; i < chick.size(); i++) { selected[i] = true; dfs(cnt + 1, start + 1); selected[i] = false; } } void input() { cin >> N >> M; city = vector<vector<int>>(N, vector<int>(N)); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> city[i][j]; if (city[i][j] == HOME) home.push_back({ i,j }); if (city[i][j] == CHICKEN) chick.push_back({ i,j }); } } } int main() { input(); dfs(0, 0); cout << ret << endl; return 0; }
결론: 테스트 케이스는 모두 통과 됐지만 메모리초과, 시간 초과 난리가 났다
Solution 2
- 시간 초과가 난 이유는
집에서 가장 가까운 치킨집까지의 거리를 탐색할 때, BFS를 사용했다는 점과 최대 m개까지 치킨집을 고를 수 있다고 했으므로 그냥m개를 골랐을 때 탐색을 하면 된다 (m개를 선택하나, m-1개를 선택하나 어차피 가까운 치킨집을 선택할 것이므로)
vector가 조금 더 느리다고 해서int city[][]로 바꾸어주고,chickSize, homeSize를 정의해주어 조금이라도 함수 접근 시간을 줄이려고 했다
m개를 골랐을 때bfs탐색을 하고, 선택된 치킨집을sChick에 넣어 관리한다
- 각각의
home에 대해sChick중에 가장 가까운sChick을 선택해 거리를 더해준다
int checkDist() {
int sum = 0;
for (int i = 0; i < homeSize; i++) {
int y = home[i].first;
int x = home[i].second;
int d = 9999999;
for (int j = 0; j < sChick.size(); j++) {
int cy = sChick[j].first;
int cx = sChick[j].second;
int dist = abs(cy - y) + abs(cx - x);
d = min(d, dist);
}
sum += d;
}
return sum;
}전체코드
#include <iostream> #include <vector> #include <cmath> #define endl "\n" using namespace std; vector <pair <int, int>> chick, home, sChick; int city[51][51]; bool selected[11]; int ret = 9999999; int N, M, chickSize, homeSize; int min(int A, int B) { if (A < B) return A; return B; } int checkDist() { int sum = 0; for (int i = 0; i < homeSize; i++) { int y = home[i].first; int x = home[i].second; int d = 9999999; for (int j = 0; j < sChick.size(); j++) { int cy = sChick[j].first; int cx = sChick[j].second; int dist = abs(cy - y) + abs(cx - x); d = min(d, dist); } sum += d; } return sum; } void dfs(int cnt, int start) { if (cnt==M) { ret=min(ret, checkDist()); return; } for (int i = start; i < chickSize; i++) { selected[i] = true; sChick.push_back(chick[i]); dfs(cnt + 1, i + 1); selected[i] = false; sChick.pop_back(); } } void input() { cin >> N >> M; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> city[i][j]; if (city[i][j] == 1) home.push_back({ i,j }); if (city[i][j] == 2) chick.push_back({ i,j }); } } chickSize = chick.size(); homeSize = home.size(); } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); input(); dfs(0, 0); cout << ret << endl; return 0; }
Backend 개발자 지망생