BOJ-백준 2188번 축사 배정 C++

BOJ-백준 2188번 축사 배정 C++ 문제 풀이 입니다.

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

2188번: 축사 배정

 

 

 

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

#include <iostream>
#include <vector>
#define MAX 201
using namespace std; 
// 축사 m 칸 소 n 마리 1 ~200
int n, m;
vector<int> cow[MAX];
int assignCow[MAX];
bool check[MAX];

bool dfs(int x) {
  for(int i=0; i<cow[x].size(); i ++){
    int t = cow[x][i]; // 소가 원하는 축사 번호
    if(check[t]) continue;
    // 현재 축사가 정해졌다면 pass
    check[t] = true;
    // 빈 축사라면 방문 check
    if(assignCow[t] == 0 || dfs(assignCow[t])){
      assignCow[t] = x;
      return true;
    }
  }
  return false;
}

int main() {
  scanf("%d %d", &n, &m);
  for(int i=1; i <=n; i ++) {
    int houseNum;
    scanf("%d",&houseNum);
    for(int j= 0; j<houseNum; j++){
      int houseNum;
      scanf("%d",&houseNum);
      cow[i].push_back(houseNum);
    }
  }
  int count = 0;
  for(int i= 1;  i<= n; i ++){
    fill(check, check+MAX, false);
    if(dfs(i)) count++;
  }
  cout<<count<<endl;
}

 

📌 해설

이분매칭을 통해 최대로 매칭될 수 있는 횟수를 구하는 문제입니다. 네트워크 플로우의 최대 유량 문제로 접근해도 동일한 개념이 적용됩니다. 

 

 

#include <iostream>
#include <vector>
#define MAX 201
using namespace std; 
// 축사 m 칸 소 n 마리 1 ~200
int n, m;
vector<int> cow[MAX];
int assignCow[MAX];
bool check[MAX];

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

1-1. n, m 은 소의 수, 축사 수 입니다. 

1-2. 소와 축사는 각각 최대 200까지 입력될 수 있으므로 MAX를 201로 정의 하였습니다. 

1-3. 벡터 cow에는 각 소들이 원하는 축사 번호를 저장합니다. 

1-4. assignCow는 배정된 소와 축사의 정보를 저장합니다. 

1번축사에 3번 소가 배정되었다면 assignCow[1] = 3 이라고 저장됩니다. 

1-5. check에는 축사가 배정 되었는지 여부를 판별하도록 bool 타입으로 선언합니다. 

 

int main() {
  scanf("%d %d", &n, &m);
  for(int i=1; i <=n; i ++) {
    int houseNum;
    scanf("%d",&houseNum);
    for(int j= 0; j<houseNum; j++){
      int houseNum;
      scanf("%d",&houseNum);
      cow[i].push_back(houseNum);
    }
  }
  int count = 0;
  for(int i= 1;  i<= n; i ++){
    fill(check, check+MAX, false);
    if(dfs(i)) count++;
  }
  cout<<count<<endl;
}

2. main 에서는 필요한 정보를 입력받고, dfs를 수행합니다.

 

bool dfs(int x) {
  for(int i=0; i<cow[x].size(); i ++){
    int t = cow[x][i]; // 소가 원하는 축사 번호
    if(check[t]) continue;
    // 현재 축사가 정해졌다면 pass
    check[t] = true;
    // 빈 축사라면 방문 check
    if(assignCow[t] == 0 || dfs(assignCow[t])){
      assignCow[t] = x;
      return true;
    }
  }
  return false;
}

3. dfs는 소의 번호를 매개변수로 넘겨 받아 해당 소가 축사 배정이 되었다면 true, 

배정이 되지 않으면 false를 반환할 수 있도록 합니다. 

3-1. x 번 소가 원하는 축사 번호들을 탐색하도록 for문을 작성합니다. 

3-2. 해당 축사 번호를 t에 저장합니다. 

3-3. 해당 축사 번호가 만약 이미 배정된 축사 번호라면 매칭을 종료합니다. 

3-4. 아직 배정이 안 되었다면 배정되었다고 변경 한 뒤, 매칭을 진행합니다.

3-5. 만약 해당 축사에 들어있는 소가 없다면( assignCow[t] == 0) 소와 축사를 매칭합니다.

3-6. 만약 해당 축사에 소가 들어있다면 dfs를 수행합니다.

그 축사에 들어있는 소 번호로 dfs수행하여 true를 반환하면 해당 축사는 소 x에게 배정됩니다. 

3-7. 모든 과정을 반복하고 dfs가 종료되면 main에서 count가 증가 합니다. 

 

 

 

::