STL(algorithm의 Sort) 활용 - Baby Gin 판별기

시뮬레이션 + DFS 문제입니다.

 

가능한 모든 경우의 수를 재귀적으로 계산하여 결과값 Ans를 갱신하는 방식으로 풀었습니다.

 

//SWEA 2112

 

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

 

#define INF 2e9

#define PURE -1

#define A 0

#define B 1

 

int D, W, K;

int Ans;

int Layer[14][21]; //두꼐 3~13, 가로크기 1~20

int BULayer[14][21];

 

void Backup(int col)

{

for (int j = 0; j < W; j++)

{

BULayer[col][j] = Layer[col][j];

}

}

 

void Restore(int col)

{

for (int j = 0; j < W; j++)

{

Layer[col][j] = BULayer[col][j];

}

}

 

bool IsPass()

{

for (int j = 0; j < W; j++)

{

int cnt = 1;

int tmp = Layer[0][j];

 

for (int i = 1; i < D; i++)

{

if (cnt >= K)

{

break;

}

 

if (tmp == Layer[i][j])

{

cnt += 1;

}

else

{

cnt = 1;

tmp = Layer[i][j];

}

}

 

if (cnt < K)

{

return false;

}

}

 

return true;

}

 

void SolveDFS(int type, int dcnt, int lcnt)

{

if (dcnt >= Ans) //pruning

{

return;

}

 

if (lcnt == D)

{

if (IsPass()) //검수 기준에 통과하는지 체크

{

Ans = min(Ans, dcnt); //통과한다면 Ans 최소값으로 갱신

}

return;

}

 

Backup(lcnt); //막의 현재 층만 백업

 

if (type == A || type == B)

{

for (int i = 0; i < W; i++)

{

Layer[lcnt][i] = type;

}

}

 

SolveDFS(PURE, dcnt, lcnt + 1);

SolveDFS(A, dcnt + 1, lcnt + 1);

SolveDFS(B, dcnt + 1, lcnt + 1);

 

Restore(lcnt); //막의 현재 층만 복원

}

 

void SolveAll()

{

SolveDFS(PURE, 0, 0);

SolveDFS(A, 1, 0);

SolveDFS(B, 1, 0);

}

 

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(0); cout.tie(0);

 

int t;

 

cin >> t;

for (int tc = 1; tc <= t; tc++)

{

Ans = INF;

memset(Layer, 0, sizeof(Layer));

memset(BULayer, 0, sizeof(BULayer));

 

cin >> D >> W >> K;

 

for (int i = 0; i < D; i++)

{

for (int j = 0; j < W; j++)

{

cin >> Layer[i][j];

}

}

 

SolveAll();

cout << "#" << tc << " " << Ans << "\n";

 

}

return 0;

}