BOJ-백준 1671번 상어의 저녁식사 C++

BOJ-백준 1671번 상어의 저녁식사 C++ 문제 풀이 입니다.

링크 : https://www.acmicpc.net/problem/1671

1671번: 상어의 저녁식사

 

 

 

✅ C++ 정답 코드 입니다. 더보기 클릭!

#include <iostream>
#include <vector>
#define MAX 1001
using namespace std;
// 상어의 총 수 n
// 크기 s 속도 v 지능 q

class Shark{
  public:
  int size;
  int velocity;
  int iq;
  Shark(int size, int velocity, int iq){
    this -> size = size;
    this -> velocity = velocity;
    this -> iq = iq;
  }
}; 

int n;
vector<Shark> sharkInfo[MAX];
vector<int> shark[MAX];
int d[MAX];
bool check[MAX];

bool dfs(int x){
  for(int i=0; i<shark[x].size(); i++) {
    int t=shark[x][i]; // 먹을 수 있는 상어
    if(check[t]) continue; // 이미 먹힌 상어라면 pass
    check[t] = true; //먹었다고 표시
    if(d[t] == 0 || dfs(d[t])){
      d[t] = x;
      return true;
    } 
  }
  return false;
}

int main() {
  cin >> n;
  for(int i=1; i<=n; i ++){
    int s, v, q;
    scanf("%d %d %d", &s, &v, &q);
    sharkInfo[i].push_back(Shark(s,v,q));
  }
  // 상어 정보를 바탕으로 트리를 새로 만든다.
  for(int i=1; i<=n-1; i++){
    for(int j=i+1; j<=n; j++){
      if(sharkInfo[i][0].size == sharkInfo[j][0].size && sharkInfo[i][0].velocity == sharkInfo[j][0].velocity && sharkInfo[i][0].iq == sharkInfo[j][0].iq){
            shark[i].push_back(j);
      } else if(sharkInfo[i][0].size <= sharkInfo[j][0].size && sharkInfo[i][0].velocity<=sharkInfo[j][0].velocity && sharkInfo[i][0].iq <= sharkInfo[j][0].iq){
            shark[j].push_back(i);
          } else if(sharkInfo[i][0].size >= sharkInfo[j][0].size && sharkInfo[i][0].velocity >= sharkInfo[j][0].velocity && sharkInfo[i][0].iq >= sharkInfo[j][0].iq){
            shark[i].push_back(j);
          } 
    }
  }
  int count=0;
  for(int i=1; i<=n; i++){
    fill(check, check+MAX, false);
    if(dfs(i)) count++;
    fill(check, check+MAX, false);
    if(dfs(i)) count++;
  }
  int k=0;
  for(int i=1; i <=n; i++){
    // 살아있는 상어 count
    if(d[i]==0){
      k++;
    }
    cout << d[i]<<' ';
  }
  cout<<endl;
  cout<<k;
  // 상어가 먹을 수 있는 정보를 담은 그래프를 통해 
  // 살아남은 상어의 수를 구함
}

 

📌 해설

이분매칭 응용 문제입니다. 상어의 저녁식사에 대한 최대 매칭 수를 구하면 (총 상어 수- 매칭 수) 로 살아남은 상어 수를 구할 수 있습니다. 

 

🚩주의

능력치가 모두 같은 상어들은 인덱스가 작은 쪽의 상어가 큰쪽의 상어를 먹을 수 있는 것으로 처리합니다.

서로를 먹게 되는 경우를 방지하기 위함입니다. 

 

 

#include <iostream>
#include <vector>
#define MAX 1001
using namespace std;
// 상어의 총 수 n
// 크기 s 속도 v 지능 q

class Shark{
  public:
  int size;
  int velocity;
  int iq;
  Shark(int size, int velocity, int iq){
    this -> size = size;
    this -> velocity = velocity;
    this -> iq = iq;
  }
};
int n;
vector<Shark> sharkInfo[MAX];
vector<int> shark[MAX];
int d[MAX];
bool check[MAX];

1. 필요한 변수를 모두 선언합니다. 

저는 Shark라는 클래스를 만들어 주고 크기, 속도, 지능에 대한 변수를 갖도록 만들었습니다.

sharkInfo에는 각 상어의 크기, 속도, 지능을 저장합니다. 

shark에는 각 상어가 저녁식사로 매칭될 수 있는 상어의 번호가 저장됩니다. 

d는 매칭 결과를 저장합니다.

check는 처리된 번호에는 true, 아직 처리되지 않았으면 false를 저장하여 방문 여부를 판별합니다. 

 

 

bool dfs(int x){
  for(int i=0; i<shark[x].size(); i++) {
    int t=shark[x][i]; // 먹을 수 있는 상어
    if(check[t]) continue; // 이미 먹힌 상어라면 pass
    check[t] = true; //먹었다고 표시
    if(d[t] == 0 || dfs(d[t])){
      d[t] = x;
      return true;
    } 
  }
  return false;
}

2. dfs로 상어 관계에 대한 탐색을 진행합니다. 매칭이 이루어질 경우 true, 매칭에 실패할 경우 false를 반환합니다.

 

int main() {
  cin >> n;
  for(int i=1; i<=n; i ++){
    int s, v, q;
    scanf("%d %d %d", &s, &v, &q);
    sharkInfo[i].push_back(Shark(s,v,q));
  }
  // 상어 정보를 바탕으로 트리를 새로 만든다.
  for(int i=1; i<=n-1; i++){
    for(int j=i+1; j<=n; j++){
      if(sharkInfo[i][0].size == sharkInfo[j][0].size && sharkInfo[i][0].velocity == sharkInfo[j][0].velocity && sharkInfo[i][0].iq == sharkInfo[j][0].iq){
            shark[i].push_back(j);
      } else if(sharkInfo[i][0].size <= sharkInfo[j][0].size && sharkInfo[i][0].velocity<=sharkInfo[j][0].velocity && sharkInfo[i][0].iq <= sharkInfo[j][0].iq){
            shark[j].push_back(i);
          } else if(sharkInfo[i][0].size >= sharkInfo[j][0].size && sharkInfo[i][0].velocity >= sharkInfo[j][0].velocity && sharkInfo[i][0].iq >= sharkInfo[j][0].iq){
            shark[i].push_back(j);
          } 
    }
  }
  int count=0;
  for(int i=1; i<=n; i++){
    fill(check, check+MAX, false);
    if(dfs(i)) count++;
    fill(check, check+MAX, false);
    if(dfs(i)) count++;
  }
  int k=0;
  for(int i=1; i <=n; i++){
    // 살아있는 상어 count
    if(d[i]==0){
      k++;
    }
    cout << d[i]<<' ';
  }
  cout<<endl;
  cout<<k;
  // 상어가 먹을 수 있는 정보를 담은 그래프를 통해 
  // 살아남은 상어의 수를 구함
}

3. main

3-1. 총 상어 수, 각 상어의 크기, 속도, 지능을 입력 받습니다. 입력 받은 정보는 sharkInfo에 저장됩니다. 

3-2. sharkInfo를 바탕으로 상어들이 먹을 수 있는 관계를 표현한 새로운 그래프 shark를 만들어 줍니다. 

    3-2.(1) 만약, 두 상어의 크기, 속도, 지능이 같을 경우 번호가 더 작은 상어가 번호가 큰 상어를 먹을 수 있는 것으로 간주합니다. (서로 잡아 먹는 경우 방지)

    3-2.(2) 상어의 스탯(크기, 속도, 지능) 3가지가 모두 다른 상어의 스탯 보다 높아야 다른 상어를 먹을 수 있습니다. 가령, 1번 상어의 스탯이 (1, 3, 3) 2번 상어의 스탯이(2, 2, 2)라면 1번 상어의 크기가 1이기 때문에 2번 상어를 먹을 수 없습니다. 

3-3.  1번 상어부터 n번 상어까지 이분매칭을 수행하는데 한 마리의 상어는 최대 두 마리까지 먹을 수 있기 때문에 한 상어당 이분매칭을 2번 수행합니다. 

3-4. 매칭이 모두 끝나면 매칭 결과에 따라 살아남은 상어의 수를 count합니다. (d[i] ==0)

 

 

::

 

이해하는 데 좀 오래 걸렸던 문제,, 알고보니 다른 곳에서 오타났던 거였던,,,ㄷㄷ