본문 바로가기

Programming/BOJ

BOJ 15686 · 치킨 배달


알고리즘 분류 : 브루트 포스  


집과 치킨집과의 거리를 각각 구해서 최소의 치킨 거리를 구하는 문제다. 여러 개의 치킨 집에서 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) 방법으로 풀 수 있다.

✓ 소스코드 보기




참고



태그

  • 감사합니다 2019.04.10 18:17 댓글주소 수정/삭제 댓글쓰기

    항상 많은 깨달음을 받아갑니다 . 감사합니다.

    선생님의 코드를 직접 그림 그려가면서 이해하는 과정에서 도저히 제 머리로는 이해가 가지 않는것이 있어서 질문드립니다..

    다름이 아니라 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는 치킨집을 고른 횟수입니다.

    • 좀 더 직관적인 조합 코드를 추가하였습니다.

    • 감사합니다 2019.04.11 21:59 댓글주소 수정/삭제

      설명을 들으니 속이 확 풀립니다.. 친절하고 명확한 답변 정말 감사드립니다 .