백준 1953 - 팀 배분 (C++)
각 학생들이 싫어하는 사람의 목록이 주어졌을 때, 모든 학생이 싫어하는 사람과 같은 팀이 되지 않도록 팀을 배분하면 된다.
5
1 3
1 5
2 1 4
1 3
1 2
위와 같이 입력이 주어진다면 아래와 같이 여러개의 정답이 나올 수 있다.
백팀 : 1, 2, 4 / 청팀 : 3, 5
백팀 : 3, 5 / 청팀 : 1, 2, 4
백팀 : 1, 4, 5 / 청팀 : 2, 3
백팀 : 2, 3 / 청팀 : 1, 4, 5
(실제로는 더 있을 수도 있다.)
이 중, 하나의 경우를 구한 뒤 출력하면 된다.
문제 풀이
각 학생들이 싫어하는 학생의 목록을 확인한 뒤, 하나씩 팀에 배분해주면 된다.
위에서 보여주었던 입력에 대해 생각해보자.
1번 학생은 3번 학생을 싫어한다.
=> 청팀 : 1 / 백팀 : 3
2번 학생은 5번 학생을 싫어한다.
=> 청팀 : 1, 2 / 백팀 : 3, 5
3번 학생은 1번 학생, 4번 학생을 싫어한다.
=> 청팀 : 1, 2, 4 / 백팀 : 3, 5
4번 학생은 3번 학생을 싫어한다.
=> 청팀 : 1, 2, 4 / 백팀 : 3, 5 (이미 팀 배분이 되어 있어, 변화가 없다.)
5번 학생은 2번 학생을 싫어한다.
=> 청팀 : 1, 2, 4 / 백팀 : 3, 5 (이미 팀 배분이 되어 있어, 변화가 없다.)
이렇게, 선택된 학생이 싫어하는 학생의 목록을 기반으로 팀에 차례대로 배분해주면 된다.
풀이 코드
std::vector<std::vector<int>> Hates;
std::vector<bool> isDevided;
//-1이면 청, 1이면 백
std::vector<int> DevidedTeam;
std::vector<int> BlueTeam;
std::vector<int> WhiteTeam;
먼저, 이렇게 5개의 벡터를 선언해주었다.
Hates는 인덱스에 해당하는 학생이 싫어하는 학생들의 목록을 저장한 벡터이다.
isDevided는 인덱스에 해당하는 학생이 싫어하는 학생들을 팀에 배분했는가를 담고 있는 벡터이다.
DevidedTeam은 학생들의 현재 팀을 저장한 벡터이다. 0이면 아직 팀 배분이 되지 않은 것이고, -1이면 청팀 1이면 백팀이다.
BlueTeam과 WhiteTeam은 각각 팀에 포함된 학생들의 목록이다.
void Recursive(int _CurIndex)
{
if (isDevided[_CurIndex] == true)
{
return;
}
isDevided[_CurIndex] = true;
if (DevidedTeam[_CurIndex] == 0)
{
DevidedTeam[_CurIndex] = -1;
}
for (int i = 0; i < Hates[_CurIndex].size(); i++)
{
int CurHateIndex = Hates[_CurIndex][i];
if (DevidedTeam[CurHateIndex] != 0)
{
continue;
}
DevidedTeam[CurHateIndex] = -DevidedTeam[_CurIndex];
Recursive(CurHateIndex);
}
}학생들이 현재 싫어하는 목록을 학생의 반대 팀에 배치한 뒤, 배치된 학생을 기준을 기준으로 함수를 재귀적으로 호출하여 다시 해당 학생이 싫어하는 학생들을 모두 반대 팀에 배치하도록 하였다.
싫어하는 학생을 배치한 학생의 인덱스에 대해 isDevided 를 true로 만들어, 같은 학생에 대해 여러 번 실행되지 않도록 하였다.
isDevided.resize(NumMan, false);
DevidedTeam.resize(NumMan, 0);
for (int i = 0; i < NumMan; i++)
{
Recursive(i);
}위의 함수를 모든 학생에 대해 실행하였다.
BlueTeam.reserve(NumMan);
WhiteTeam.reserve(NumMan);
for (int i = 0; i < NumMan; i++)
{
if (DevidedTeam[i] == -1)
{
BlueTeam.push_back(i + 1);
}
else if (DevidedTeam[i] == 1)
{
WhiteTeam.push_back(i + 1);
}
}
std::cout << BlueTeam.size() << "\n";
for (int i = 0; i < BlueTeam.size(); i++)
{
std::cout << BlueTeam[i] << " ";
}
std::cout << "\n";
std::cout << WhiteTeam.size() << "\n";
for (int i = 0; i < WhiteTeam.size(); i++)
{
std::cout << WhiteTeam[i] << " ";
}학생들이 배치된 팀에 따라, 각 벡터에 삽입하였고, 해당 벡터의 사이즈와 원소를 모두 출력해주었다.
코드 전문
#include <iostream>
#include <vector>
void Init()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
}
std::vector<std::vector<int>> Hates;
std::vector<bool> isDevided;
//-1이면 청, 1이면 백
std::vector<int> DevidedTeam;
std::vector<int> BlueTeam;
std::vector<int> WhiteTeam;
void Recursive(int _CurIndex)
{
if (isDevided[_CurIndex] == true)
{
return;
}
isDevided[_CurIndex] = true;
if (DevidedTeam[_CurIndex] == 0)
{
DevidedTeam[_CurIndex] = -1;
}
for (int i = 0; i < Hates[_CurIndex].size(); i++)
{
int CurHateIndex = Hates[_CurIndex][i];
if (DevidedTeam[CurHateIndex] != 0)
{
continue;
}
DevidedTeam[CurHateIndex] = -DevidedTeam[_CurIndex];
Recursive(CurHateIndex);
}
}
int main()
{
Init();
int NumMan = 0;
std::cin >> NumMan;
Hates.resize(NumMan);
for (int i = 0; i < NumMan; i++)
{
int NumHate = 0;
std::cin >> NumHate;
Hates[i].reserve(NumHate);
for (int j = 0; j < NumHate; j++)
{
int HateMan = 0;
std::cin >> HateMan;
Hates[i].push_back(HateMan - 1);
}
}
isDevided.resize(NumMan, false);
DevidedTeam.resize(NumMan, 0);
for (int i = 0; i < NumMan; i++)
{
Recursive(i);
}
BlueTeam.reserve(NumMan);
WhiteTeam.reserve(NumMan);
for (int i = 0; i < NumMan; i++)
{
if (DevidedTeam[i] == -1)
{
BlueTeam.push_back(i + 1);
}
else if (DevidedTeam[i] == 1)
{
WhiteTeam.push_back(i + 1);
}
}
std::cout << BlueTeam.size() << "\n";
for (int i = 0; i < BlueTeam.size(); i++)
{
std::cout << BlueTeam[i] << " ";
}
std::cout << "\n";
std::cout << WhiteTeam.size() << "\n";
for (int i = 0; i < WhiteTeam.size(); i++)
{
std::cout << WhiteTeam[i] << " ";
}
return 0;
}