[백준/BOJ] 12886번 돌 그룹 (C++)

www.acmicpc.net/problem/12886

12886번: 돌 그룹

BFS 유형의 문제입니다.

메모리 초과로 인해 해당 블로그를 참고하여 문제를 해결했습니다. 포인트는 숫자가 3개로 고정되어 있기 때문에, 배열을 2개만 사용해도 된다는 점이었습니다.

 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int a, b, c, d;
bool visit[501][501]; // 숫자가 3개로 고정, 따라서 배열을 2개만 사용해도 된다. (3개 사용하면 메모리 초과)

int BFS() {
    queue<pair<int, int > > q;
    q.push({a, b});
    visit[a][b] = true;
    
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        int z = d - (x + y);
        q.pop();
        
        if(x == y && y == z) return 1;
        
        // (x, y), (y, z), (x, z) 결정
        int dx[3] = {x, x, y};
        int dy[3] = {y, z, z};
        
        for(int i = 0; i < 3; i++) {
            int nx = dx[i];
            int ny = dy[i];
            if(nx < ny) ny -= nx, nx += nx;
            else if(nx > ny) nx -= ny, ny += ny;
            else continue;
            
            // 합을 통해 나머지 하나의 값을 구할 수 있고, 최소값과 최대값만 사용한다.
            int nz = d - (nx + ny); 
            int nxx = min(nx, min(ny, nz));
            int nyy = max(nx, max(ny, nz));
            
            if(!visit[nxx][nyy]) {
                q.push({nxx, nyy});
                visit[nxx][nyy] = true;
            }
        }
    }
    
    return 0;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
 
    cin >> a >> b >> c;
    d = a + b + c;
    if(d % 3 == 0) cout << BFS();
    else cout << "0";
}