Logo냥냠감자기술 블로그
Skip to Content
AlgorithmBinary Search (3)상어의 저녁식사
작성일: 2024-01-12

문제

백준 1671 - 상어의 저녁식사 

  • 난이도: 플레3
  • 알고리즘: 이분 매칭

코드

#include <algorithm> #include <iostream> #include <vector> using namespace std; struct Info { int values[3]; int index; }; int sharkNum; bool checkCanEat(Info &infoMe, Info &infoOther) { bool allGreater = true; for (int i = 0; i < 3; i++) { if (infoMe.values[i] < infoOther.values[i]) { allGreater = false; break; } } bool allSame = true; for (int i = 0; i < 3; i++) { if (infoMe.values[i] != infoOther.values[i]) { allSame = false; break; } } if (allSame) { return infoMe.index < infoOther.index; } else { return allGreater; } } bool dfs(vector<vector<int>> &availToEat, vector<int> &matching, vector<bool> &visited, int sharkIndex) { for (int i = 0; i < availToEat[sharkIndex].size(); i++) { int currOtherIndex = availToEat[sharkIndex][i]; if (visited[currOtherIndex]) { continue; } visited[currOtherIndex] = true; if (matching[currOtherIndex] == -1 || dfs(availToEat, matching, visited, matching[currOtherIndex])) { matching[currOtherIndex] = sharkIndex; return true; } } return false; } int main() { cin >> sharkNum; vector<Info> infos(sharkNum); for (int i = 0; i < sharkNum; i++) { Info currInfo; cin >> currInfo.values[0] >> currInfo.values[1] >> currInfo.values[2]; currInfo.index = i; infos[i] = currInfo; } int cnt = 0; vector<vector<int>> availToEat(sharkNum, vector<int>()); for (int i = 0; i < sharkNum; i++) { for (int j = 0; j < sharkNum; j++) { if (i == j) { continue; } if (checkCanEat(infos[i], infos[j])) { availToEat[i].push_back(j); } } } vector<int> matching(sharkNum, -1); for (int i = 0; i < sharkNum; i++) { vector<bool> visited(sharkNum, false); if (dfs(availToEat, matching, visited, i)) { cnt++; } } for (int i = 0; i < sharkNum; i++) { vector<bool> visited(sharkNum, false); if (dfs(availToEat, matching, visited, i)) { cnt++; } } cout << sharkNum - cnt; }

회고

이분 매칭 개념의 난이도도 조금 있을 뿐더러 이 문제는 이분 매칭을 적용해보자는 발상을 하는것 역시 어려운 문제였다. 나는 이분 매칭 문제를 풀어보고 싶어 처음부터 이분 매칭 문제를 찾아서 푼 것이기 때문에 훨씬 쉽게 푼 감이 있다. 아마 대회나 시험 등에서 이런 문제를 마주쳤다면 이분매칭을 떠올리지 못할지도 모르겠다…