[dfs/ bfs] [정점의 재정의] 돌 그룹

문제 해설 및 주의사항

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.

강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.

크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.

A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.

첫째 줄에 A, B, C가 주어진다. (1 ≤ A, B, C ≤ 500)

돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력한다.

 

---

 

풀이

1. 정점의 정의

: (a, b, c) 각 돌의 개수

 

2. 정점의 개수

: 각 정점의 크기가 1500 이하일 것이다. (1500)^3 = 33억. 너무 크다.

정점의 정의를 바꾸어야 한다. 

 

정점을 (a, b) 로만 두는 것이다. 전체 돌의 개수는 a+b+c 이므로, 나머지 정점은 자연스럽게 구할 수 있다.

1500^2 = 225만 이므로, 충분히 가능하다.

---

풀이코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

const int MAX = 1500;

bool check[MAX + 1][MAX + 1];
int sum;

void dfs(int x, int y){
	// 방문했었다면 끝
	if(check[x][y]) return;
	check[x][y] = true;
	
	int stones[3] = {x, y, sum - (x + y)};
	
	// a, b, c 세 그룹을 각각 비교해보기 위함
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++){
			if(stones[i] < stones[j]){
				// 현재 x, y 정점에서의 stones 값을 변화시키지 않기 위해 tmp 에 값을 더한다.
				int tmp[3] = {x, y, sum - (x + y)};
				tmp[i] += stones[i];
				tmp[j] -= stones[i];
				
				dfs(tmp[0], tmp[1]);
			}
		}
	}
}

int main(){
	int x, y, z;
	cin >> x >> y >> z;
	sum = x + y + z;
	
	// 합이 3의 배수가 아니면 불가능
	if(sum % 3 != 0){
		cout << 0 << '\n';
		return 0;
	}
	
	dfs(x, y);
	
	// x, y, z 가 같은 값이 되었으면 sum / 3 인 값을 가질 것이다.
	if(check[sum / 3][sum / 3]){
		cout << 1 << '\n';
	}
	else{
		cout << 0 << '\n';
	}
}

 

---

퇴고

1. 문제 풀이의 흐름

 

a. 정점을 정의했다. (x,  y, z)

b. 계산해보니 정점의 크기가 너무 크다. 시간과 메모리가 많이 요구된다.

c. 총 정점의 크기를 줄이기 위해 정점을 재정의했다. (x, y)

 

2. 과신

- 한 정점 (x, y) 에서 다른 정점으로 갈 수 있는 경우는 총 6가지이다. 그것을 간과하고 자신보다 큰 인덱스랑만 비교하였어서 틀린 값이 나왔다. 모든 간선을 방문해야 dfs 이다.