백준 12866 - 돌 그룹 (C++)
3개의 돌 그룹이 있다. 각 그룹에는 돌이 A개, B개, C개씩 포함되어있다.
이 때, 두 개의 돌 그룹을 선택하여 돌의 개수를 바꾸는 연산을 진행한다.
개수를 바꾸는 진행은 두 그룹의 돌 개수가 X, Y 이고, X < Y라고 했을 때, X = 2 * X , Y = Y - X 의 형식으로 진행한다.
이 연산을 반복하여 A,B,C의 개수를 모두 동일하게 만들 수 있다면 1을 출력하고, 아니라면 0을 출력하면 된다.
문제 풀이
이 문제는 모든 경우를 탐색하는 방법 말고는 더 좋은 방법은 딱히 없는 듯 하다.
방문 체크를 하며, 이미 탐색한 경우는 제외하고 모든 경우에 대해 탐색하도록 하였다.
최초에 A, B, C가 주어진다.
연산은 두 그룹을 선택했을 때, 더 작은 쪽의 값을 작은 쪽에 더하고, 큰 쪽에서 빼는 연산을 하게 된다.
같은 양을 양쪽에 빼고 더하기 때문에, 전체 총량 (A + B + C)는 변하지 않는다.
즉, A와 B만 알면 사실 C는 구할 수 있다.
이 아이디어를 기준으로, 방문 체크는 3차원 배열이 아닌 2차원 배열을 사용하여 2개의 돌을 기준으로만 하게 된다.
또한, 1, 2, 3 과 3, 2, 1은 사실 같은 경우라고 할 수 있다.
문제에서 구하는 것은 연산을 반복했을 때, 모든 돌 그룹의 돌 개수가 같아질 수 있는지 여부를 반환하는 것이기 때문에 1,2,3 에서 true가 나온다면 3, 2,1에서도 당연히 true가 나올 수 밖에 없다.
그렇기 때문에, 돌 개수를 정렬하여 탐색을 할 것이다.
(1, 2, 3 과 3, 2, 1을 같은 경우라고 가정하기 위해)
처음 A, B, C가 있다면, 이 중 2개의 돌 A, B만 선택하여 Queue에 삽입한다.
이후, Queue에서는 front를 pop한 뒤, A,B,C를 기준으로 BFS를 진행할 것이다.
1. A, B를 선택하는 경우
2. A, C를 선택하는 경우
3. B, C를 선택하는 경우
세 경우를 탐색하며 계속 BFS를 진행하며, A,B,C가 같아지는 타이밍이 온다면 1을 출력하고 종료하도록 하였다.
만약, BFS가 모두 끝날 때 까지 A,B,C가 같아지는 타이밍을 발견하지 못한다면 0을 출력하도록 하였다.
또한, A, B, C 가 절대 같아질 수 없는 경우가 한 가지 있는데, A + B + C의 값이 3의 배수가 아닌 경우이다.
A, B, C가 모두 X라는 값으로 같은 값을 가진다면 A + B + C 는 3X 가 된다.
즉, A, B, C 가 같다면, A + B + C 는 반드시 3의 배수여야 한다.
그러므로, A + B + C가 3의 배수가 아니라면 바로 0을 출력하고 종료하도록 예외처리를 해주었다.
풀이 코드
int A = 0;
int B = 0;
int C = 0;
std::cin >> A >> B >> C;
int SumStone = A + B + C;
if (SumStone % 3 != 0)
{
std::cout << 0;
return 0;
}먼저, 입력을 받아준 뒤 세 수의 합이 3의 배수가 아니라면 0을 출력한 뒤 종료하도록 하였다.
std::queue<std::pair<int, int>> BFS;
if (A > B)
{
std::swap(A, B);
}
BFS.push({A, B});다음은 queue에 첫 원소인 {A, B}를 삽입해 주었다.
이 때, A와 B를 오름차순으로 정렬하여 넣어주어야 한다.
while (BFS.size() > 0)
{
std::pair<int, int> CurStone = BFS.front();
BFS.pop();
int A = CurStone.first;
int B = CurStone.second;
int C = SumStone - A - B;
if (A == B && B == C)
{
std::cout << 1;
return 0;
}
if (A != B)
{
InsertQueue(A, B, BFS);
}
if (B != C)
{
InsertQueue(B, C, BFS);
}
if (A != C)
{
InsertQueue(A, C, BFS);
}
}BFS내부 코드이다.
먼저, C를 구해준다. 그리고, A와 B와 C가 모두 같은지 검사해준다. 만약 같다면 1을 출력하고 그대로 종료한다.
같지 않다면, 그대로 너비 우선 탐색을 진행한다.
두 그룹을 선택했을 때, 돌의 개수가 같다면 선택할 수 없으므로 두 그룹의 돌 개수가 다른 경우에만 탐색을 진행하도록 하였다.
void InsertQueue(int _Left, int _Right, std::queue<std::pair<int, int>>& _Queue)
{
if (_Left > _Right)
{
std::swap(_Left, _Right);
}
_Right -= _Left;
_Left *= 2;
if (isVisit[_Left][_Right] == false)
{
isVisit[_Left][_Right] = true;
_Queue.push({ _Left, _Right });
}
}이는 queue에 원소를 삽입하는 함수이다.
동일한 코드를 여러 번 작성하는 것이 불편하니, 함수로 만들어주었다.
먼저, 선택된 두 숫자를 오름차순으로 정렬하였다.
그리고, 연산을 진행하였다. 큰 수에서는 작은 수를 빼주고, 작은 수에는 작은 수를 더해주었다.
그렇게 나온 경우를 이미 탐색한 경험이 없다면, 방문 체크를 한 뒤 queue에 삽입해주었다.
std::cout << 0;
return 0;만약, 반복문이 끝날 때 까지 프로그램이 종료되지 않았다면 세 그룹의 돌 개수가 같은 경우를 발견하지 못한 것이므로 0을 출력하고 끝내주었다.
코드 전문
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
void Init()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
}
std::vector<std::vector<bool>> isVisit(1501, std::vector<bool>(1501, false));
void InsertQueue(int _Left, int _Right, std::queue<std::pair<int, int>>& _Queue)
{
if (_Left > _Right)
{
std::swap(_Left, _Right);
}
_Right -= _Left;
_Left *= 2;
if (isVisit[_Left][_Right] == false)
{
isVisit[_Left][_Right] = true;
_Queue.push({ _Left, _Right });
}
}
int main()
{
Init();
int A = 0;
int B = 0;
int C = 0;
std::cin >> A >> B >> C;
int SumStone = A + B + C;
if (SumStone % 3 != 0)
{
std::cout << 0;
return 0;
}
std::queue<std::pair<int, int>> BFS;
if (A > B)
{
std::swap(A, B);
}
BFS.push({A, B});
while (BFS.size() > 0)
{
std::pair<int, int> CurStone = BFS.front();
BFS.pop();
int A = CurStone.first;
int B = CurStone.second;
int C = SumStone - A - B;
if (A == B && B == C)
{
std::cout << 1;
return 0;
}
if (A != B)
{
InsertQueue(A, B, BFS);
}
if (B != C)
{
InsertQueue(B, C, BFS);
}
if (A != C)
{
InsertQueue(A, C, BFS);
}
}
std::cout << 0;
return 0;
}