반응형
알고리즘 분류 : 브루트 포스
집과 치킨집과의 거리를 각각 구해서 최소의 치킨 거리를 구하는 문제다. 여러 개의 치킨 집에서 M개의 치킨 집을 고른 후, 문제에 주어진 조건대로 치킨 거리를 구해서 답을 찾아야 한다.
- 입력받을 때, 치킨집(2)의 개수와 집(1)의 개수를 세고, 각 좌표 (X, Y)를 리스트에 저장한다.
- 치킨집의 총 개수를 K개라고 할 때, 재귀 함수를 통해 K개 중 M개를 골라야 한다. 조합 방식으로 고르면 된다.
- M개의 치킨집을 모두 고르면, 집과 치킨집과의 치킨거리를 구하고, 그중 최솟값을 정답으로 한다.
C++ 소스코드
#include <cstdio> #include <vector> #include <algorithm> using namespace std; struct pos { int x, y; }; int n, m, ans=1e9; vector<pos> home, chicken; vector<int> v; void solve(int idx, int cnt) { if (idx > (int)chicken.size()) return; if (cnt == m) { int sum = 0; for (int i=0; i<(int)home.size(); i++) { int d = 1e9; for (auto j : v) { d = min(d, abs(home[i].x-chicken[j].x)+abs(home[i].y-chicken[j].y)); } sum += d; } ans = min(ans, sum); return; } v.push_back(idx); solve(idx+1, cnt+1); v.pop_back(); solve(idx+1, cnt); } int main() { scanf("%d %d", &n, &m); for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) { int a; scanf("%d", &a); if (a == 1) home.push_back({i, j}); else if (a == 2) chicken.push_back({i, j}); } } solve(0, 0); printf("%d\n", ans); return 0; }
✓ for 문과 재귀를 이용하여 조합을 만들 수 있다.
Python 3 소스코드
n, m = map(int, input().split()) a = [list(map(int, input().split())) for _ in range(n)] home, chicken, v = [], [], [] ans = 1e9 def solve(idx, cnt): global ans if idx > len(chicken): return if cnt == m: s = 0 for hx, hy in home: d = 1e9 for j in v: cx, cy = chicken[j] d = min(d, abs(hx-cx)+abs(hy-cy)) s += d ans = min(ans, s) return v.append(idx) solve(idx+1, cnt+1) v.pop() solve(idx+1, cnt) for i in range(n): for j in range(n): if a[i][j] == 1: home.append((i+1, j+1)) elif a[i][j] == 2: chicken.append((i+1, j+1)) solve(0, 0) print(ans)
✓ 파이썬은 itertools의 combinations를 이용하여, 조합(Combination) 방법으로 풀 수 있다.
참고
- 백준 온라인 저지 : BOJ 15686
반응형
선생님의 코드를 직접 그림 그려가면서 이해하는 과정에서 도저히 제 머리로는 이해가 가지 않는것이 있어서 질문드립니다..
다름이 아니라 c++ 15라인에서의 if문 관련하여 idx > = chicken.size() 처럼, =가 붙는게 맞다고 생각하는데
(치킨집이 존재하지 않는 인덱스를 v 벡터에 넣을 필요가 없다고 생각하여 이렇게 판단하였습니다.)
결국은 다른 결과가 나오는데 혹시 왜 idx > chicken.size() 처럼 , = 를 빼셧는지 가르침을 주실수있을까요 ?
도움드릴 수 있어서 보람차네요. 감사합니다.
질문하신 것처럼 15라인에서 등호가 포함되지 않는 이유는 16라인의 치킨 count 비교보다 먼저 확인하기 때문입니다.
말씀하신 논리로 접근한다면, 먼저 if (cnt == m) 비교를 하여 return 시킨 후, 이후에 if (idx == chicken.size()) 비교를 하여 return 시키면 됩니다.
이렇게 수정하는 것이 더 효율적인 코드가 되겠네요.
solve() 함수 내부의 첫 라인에 아래 코드를 넣어서 디버깅해보시는 것을 추천드립니다.
printf("current : %d | count %d\n", idx, cnt);
current는 현재 치킨집의 번호이며, count는 치킨집을 고른 횟수입니다.
혹시 파이썬 코드에서 치킨이랑 홈 리스트에 좌표 넣을떄 i+1 j+1 해서 넣는이유가 무엇인가요..