inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

86. 피자 배달 거리(DFS활용)

맞는지 모르겠습니다

158

예리얼

작성한 질문수 5

0

선생님 저는 문제를 잘 이해하지 못한건지;; 이렇게 짰습니다

첫번째로 pizza라는 페어를 새로 만들어서 할당해도 괜찮은지 궁금합니다

그리고 강의에서는 dis = min(dis) 이렇게 하셨는데 이게 이해가 안갑니다

모든 집에서 선택된 피자가게까지의 거리를 더한 후에 그것의 min 값을 구하는 문제가 아닌가요..?

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int n, m, res;
vector<pair<int, int> > map[30];
pair<int, int> pizza[30];
dfs(int s, int L){
    if(L==m){
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                sum += abs(map[1][i].first-map[2][j].first) + abs(map[1][i].second-map[2][j].second);
            }
        }
        if(res>sum) res=sum;
    }
    else{
        for(int j=s;j<map[2].size();j++){
            pizza[j] = map[2][j];
            dfs(j+1,L+1);
            pizza[j] = {0,0};
        }
    }
}

int main(){
    int x;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&x);
            if(x==1){
                map[1].push_back(make_pair(i,j));
            }
            else if(x==2){
                map[2].push_back(make_pair(i,j));
            }
        }
    }

    dfs(0,0);
    return 0;
}

C++ 코테 준비 같이 해요!

답변 1

1

김태원

안녕하세요^^

문제에 보면

"도시에는 각 집마다 “피자배달거리”가 았는데 각 집의 피자배달거리는 해당 집과 도시의 존재 하는 피자집들과의 거리 중 최소값을 해당 집의 “피자배달거리”라고 한다. "

라고 써져 있습니다. 님은 어떤 집의 "피자배달거리" 를 해당집과 모든 피자집과의 거리의 합으로 오해한 것 같습니다.  

문제에서는 어떤 집의 "피자배달거리" 는 해당집과 각 피자집과의 거리들 중 최소값을 그 집의 "피자배달거리"로 정의하고 있습니다.

그리고 도시의 피자배달거리는 모든 집의 "피자배달거리"를 합한 것입니다.

즉 이문제는 도시의 피자배달거리가 최소가 되도록 지도의 있는 피자집 중에서 살리고자 하는 M개의 피자집을 선택해야 하는 문제로 해석할 수 있습니다.

0

예리얼

감사합니다 코테 볼때도 이런 실수 많이했는데 어렵네요 ㅜㅜ

테스트 케이스 질문

0

370

1

병합정렬 시간복잡도 질문

0

459

1

41.연속된 자연수의 합 문제풀이에서 수학적인 원리를 모르고 있습니다.

0

1340

2

질문드립니다.

0

373

1

질문드립니다!

0

427

1

dev 프로그램 질문

0

272

1

문제가 이해가 안되요

0

371

1

4번 나이차이 문제 접근법 질문 드립니다.

0

303

1

source file not compiled

0

1032

3

59번 질문드립니다.

0

368

1

25번 문제 질문

0

343

1

4. 나이차이 문제 질문입니다.

0

365

1

90번 라이언 킹 심바 1번 테스트 케이스

0

465

1

71번 문제 전역 변수 질문 있습니다

0

355

1

75번, 79번 priority_queue관련

1

351

1

75.최대 수입 스케줄

0

394

2

복면산 정답의 수

0

426

1

테스트 케이스에 대해서

0

441

1

수업 내용 질문입니다!

1

227

1

풀어보면 좋은 문제 목록 - 2580 스토쿠 DFS 질문입니다!!

0

814

2

12. 플로이드-와샬(그래프 최단거리) . 27:25초

0

249

1

다른 풀이 방식

0

313

1

크루스칼 vs 프림

0

302

1

숫자 총개수 small 질문있습니다.

0

233

1