인프런 커뮤니티 질문&답변

안녕하세요 은정님 ㅎㅎ

코드리뷰를 드리면요.

pick 함수 플로우 부분

pick함수는 해당 치킨집을 고르느냐. 안고르느냐죠?

o o

x x

이렇게 가는거 아닌가요?

    }

    pick(idx + 1, true);
    pick(idx + 1, false);
}

이런 부분은 괜찮습니다.

그러나.

    if(m > 1){

        for (int i = 0; i < cPos.size(); i++)
        {
            pick(i, true);

처음 index에서 초기에 pick을 한번 호출해야 하는 것 아닌가요?

치킨집리셋

            //cout << cnt << "번째 조합의 치킨 도시 거리는 " << minCityCD <<'\n';
            minCityCD = min(minCityCD, cityCD);
        }

        // cout << "치킨집 리셋\n";
        b[cPos[idx].first][cPos[idx].second] = 0;

지금 pick에도 리셋부분이 되어있고 그 다음에도 리셋이 되어있습니다.

            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    if (b[i][j] == 2)
                        b[i][j] = 0;
                }
            }

중복됩니다.

정확히 해당 경우의 수 -> 리셋 이런식으로 수정해야 합니다.

그리고 b라는 2차원 배열을 굳이 만들 필요가 없습니다.

제가 조금 다듬어봤습니다. 모듈화 + 은정님 true, false -> vector화 시켰습니다.

#include <bits/stdc++.h>
using namespace std;

int n, m;
int a[51][51];
vector<pair<int, int>> cPos, hPos;
int minCityCD = INT_MAX;

void calculateCityCD(const vector<int>& selected) {
    int cityCD = 0;
    for (auto& h : hPos) {
        int minCD = INT_MAX;
        for (int idx : selected) {
            auto& c = cPos[idx];
            int CD = abs(h.first - c.first) + abs(h.second - c.second);
            minCD = min(CD, minCD);
        }
        cityCD += minCD;
    }
    minCityCD = min(minCityCD, cityCD);
}

void pick(int idx = 0, vector<int> selected = {}) { 
    
    if (selected.size() > m) return; 
    if (idx == cPos.size()) {
        if (selected.size() <= m && !selected.empty()) {
            calculateCityCD(selected);
        }
        return;
    }
    // 은정님 true
    selected.push_back(idx);
    pick(idx + 1, selected);
     
    // 은정님 false
    selected.pop_back();
    pick(idx + 1, selected);
}

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) hPos.push_back({i, j});
            if (a[i][j] == 2) cPos.push_back({i, j});
        }
    }

    pick();  
    cout << minCityCD;  
}

이런 로직을 의도하신게 아닌지...

이렇게 해보시겠어요?

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.