1595. Minimum Cost to Connect Two Groups of Points
문제의 해결 방법에 대한 접근법을 다시 한번 정리하고자 작성하는 글.
이 글을 참고하였다.
처음 문제를 읽고 생각한 풀이 방법.
- DP접근을 하기 위하여서, 가로, 세로등의 사이즈가 더 작은 상태로의 Subproblem으로 적절하게 나눌 수 있을까? -> 불가능 할 것 이라는 판단.
Why? 기본적으로 Greedy하게 선택을 해야할 것 같았고, 그러기에 가로/세로를 하나씩 제한한 상태에서 Greedy하게 접근하는 것은 이전 state의 변경이 필요하므로 불가능하다고 판단.
예를 들어, [[1,2][5,10]]인 input에서 처음에 select한 1이 결과적으로는 1+10 > 2+5 이므로, 최적이 아닌 상태가 됨.
-
Backtracking을 통하여서 하나씩 접근할 수 있을까? -> 8 Queen 문제와 유사하게 가로/세로의 2차원 vector로 정의되어있는 input이므로, select되지 않은 가로/세로열을 하나씩 선택하여 적절한 상태에서 최소값을 정할 수 있을 것. -> 다만 불가능 하다고 판단. why? 12*12 인 배열에서의 backtracking은 2^(12*12) = 상당히 큰 수이고, 1번 접근과 유사하게 greedy하게 할 수 없음을 인지.
-
Graph의 풀이방법을 적용할 수 있지 않을까? -> MST와 유사하게 전체 node를 연결하는 방법에서 착안하여 group1 과 gruop2의 모든 node를 연결할 수 있지 않을까? -> PQ를 사용하여 접근하려고 하였지만, 다음과 같은 상황에서의 해결책을 제안하기 어려웠음.
[[1,1,1],[1,1,1],[1,1,1]] 에서, 각 row, col별 최소값을 정한 상태에서, (1,2)와 (2,1)의 값의 합 > (2,2)의 val이므로, 이 케이스에서 두 값을 삭제한 다음, 하나의 값을 다시 insert하는 접근으로 시도해보고자 함. but, '이상적인' 순서대로 합쳤을 경우에만 가능하나, 이를 implement하는 것은 pq이상의 다른 정렬이 필요하다고 느꼈고, 상당히 제한적인 경우에만 사용이 가능하였음.
class Solution {
public:
struct node {
int y;
int x;
int val;
node(int i, int j, int k) : y(i), x(j), val(k) {};
};
struct comp {
bool operator()(const node& n1, const node& n2){
return n1.val < n2.val;
}
};
int connectTwoGroups(vector<vector<int>>& cost) {
int m = cost.size();
int n = cost[0].size();
priority_queue<node, vector<node>, comp> pq;
set<pair<int, int>> nums;
unordered_map<int, set<int>> cols, rows;
for(int i = 0; i < m; i++){
int midx = 0;
for(int j = 0; j < n; j++){
if(cost[i][j] < cost[i][midx]) midx = j;
}
if(nums.insert({i, midx}).second){
pq.push({i, midx, cost[i][midx]});
rows[i].insert(midx);
}
}
for(int j = 0; j < n; j++){
int midx = 0;
for(int i = 0; i < m; i++){
if(cost[i][j] < cost[midx][j]) midx = i;
}
if(nums.insert({midx, j}).second){
pq.push({midx, j, cost[midx][j]});
cols[midx].insert(j);
}
}
int ans = 0;
while(!pq.empty()){
auto p = pq.top(); pq.pop();
int cury = p.y;
int curx = p.x;
if(cols[cury].size() <= 1 || rows[curx].size() <= 1) {
ans += p.val;
}
rows[cury].erase(curx);
cols[curx].erase(cury);
}
return ans;
}
};예시로 된 경우에 답을 내는데 실패한 코드
- Union-Find로 root를 찾아 같은 Group으로 만들면 되지 않을까? -> 이 문제의 경우 각 row와 각 col은 하나 이상의 col, row와 연결되었어야 하기 때문에, union-find에 대한 root를 정하는 방식이 제한적임.
그럼 어떻게 접근을 하였어야 했는가?
위 시행착오에 대하여 생각하여볼때, 이 문제는 greedy한 방식으로 해결할 수 없으며, 각 경우에 대한 최적의 상태를 전부 탐색하여야 가능한 문제 -> Brute force로 해결 할 수 있음 -> 이를 최적화한 DP문제로 귀결됨을 알 수 있음.
그렇다면 처음에 떠올렸던 DP 접근 방식과 brute force 방법에서 improve된 DP의 차이점이 무엇이었는가?
DP의 implementation에 따른 2가지 특징이 있다면 (사실 subproblem을 해결한다는 관점에서 동일하기는 하나, 생각의 전개 방식에서 차이가 있다고 생각한다), 하나는 해당 문제를 단순히 더 작은 input size로 변경하여 푸는 것, 그리고 하나는 무수히 반복되는 (brute force) 문제의 답을 빠르게 구하는 것에 있다는 것 이렇게 생각할 수 있다.
즉, 나는 1번째 DP만을 생각하여, 단순 input size를 줄여나갔을 때, 그 방법이 이미 최적의 결과를 가지고 있기에, 이전의 결과를 쌓아나가서 최적의 결론에 도달한다는 관점에서만 접근을 하였지, 결과적으로 모든 연산을 해야하는 상황에서 DP를 통해 연산량을 줄인다는 관점을 생각하지 못하였다고 할 수 있음.
Programmers에서 화살표가 뒤집히는 경우의 문제, 이 문제가 결과적으로는 DP의 2번째 특징을 이용하여 해결 할 수 있다는 점..
정리하자면,
본 문제는, 모든 경우를 계산하였어야 하고, 그 경우가 단순히 input layer를 쌓아올리는 식으로의 접근에 국한되지 않는 방식의 DP를 사용하였어야 함을 안다.
즉, '어떤 특정한 state'에 대한 DP를 어떻게 implement하는가? 에 대한 문제임을 이해할 수 있어야 했다.
여기서 중요한 힌트는, input size의 가로와 세로가 maximum 12라는 것? -> bit masking을 통해서 내가 어떤 group을 연결했는지 하나의 int 변수로 간단하게 나타낼 수 있다는 점이다.
구현은 어떻게 하는가?
위의 모든 생각을 바탕으로, row와, column 정보에 대한 dp table이 필요함을 느꼈기에, DP table을 row의 i와, 현재 연결되어 있는 group에 대한 정보인 masking 변수를 사용하여 생성한다.
int[13][4048]매 dp 함수를 호출하는 기준은 특정 row i에 대한 call이고, 이때 table정보에 i와 그 당시 masking 에 대한 결과가 이미 계산되어 있다면, 그 값을 사용하며, 그렇지 않은 경우 모든 j값에 대한 dp호출을 통하여 min값을 계산한다.
게다가, 마지막 처리에 대한 부분 또한 중요한데, 마지막 row까지 탐색하였을 때는 어떤 결과를 return할 것인가에 대한 생각으로는, 각 column이 select할 수 있는 minimum row값을 선택하게 만든다는 것 또한 중용한 포인트가 된다.
class Solution {
public:
// 처음 dp table 초기화. cost 가 0이 될 수도 있기 때문에, 최초 initialize를 -1등으로 해도 되지만, 0으로 하되, 결과값의 +1을 저장하는 식으로 하여, dp table의 값이 0이라면 계산이 되어있지 않은 상태로 판단.
int dp[13][4096] = {};
int calc(vector<vector<int>>& cost, vector<int>& table, int i, int mask){
// 앞서 dp table에 저장할 때 1보다 큰 수를 넣었기 때문에, 미리 계산된 dp table값을 return 할 때는 1을 빼준 값을 return 한다.
if(dp[i][mask]) return dp[i][mask]-1;
// row의 끝에 도달하였는 경우, 각 colume에서 선택할 수 있는 최소값을 선택할 것이고, 그렇기에 res값의 초기화 값이 달라진다.
int res = i >= cost.size() ? 0 : INT_MAX;
// 위와 마찬가지
if(i >= cost.size())
for(int k = 0; k < table.size(); k++)
// masking되어있지 않은 colume이 선택하는 값은 min값.
res += table[k] * ((mask & (1 << k)) == 0);
else
for(int k = 0; k < table.size(); k++)
// dp의 핵심. 전체를 계산한다.
res = min(res, cost[i][k] + calc(cost, table, i+1, mask | (1 << k)));
dp[i][mask] = res + 1;
return res;
}
int connectTwoGroups(vector<vector<int>>& cost) {
vector<int> table(cost[0].size(), INT_MAX);
for(int j = 0; j < cost[0].size(); j++){
for(int i = 0; i < cost.size(); i++){
table[j] = min(table[j], cost[i][j]);
}
}
return calc(cost, table, 0, 0);
}
};모든 DP문제가 그렇듯, 적고나면 별 것 아닌것 같지만, 그 해결 방법까지 도달하는 것이 DP문제의 진가가 아닌가 싶다.!
DP문제의 두가지 방향성, table의 initialize와 관련된 테크닉에 대한 연습이 필요할 것 같다.
