BOJ 2641 다각형그리기

사용한 알고리즘

시뮬레이션

알고리즘 설명

단순하다 본래 주어진 A의 순서와 B의 순서가 같으면 된다.
여기서 A와 B의 순열이 같으면서 다른경우는 아래와 같다.
Case1. A와 B의 순열의 시작점이 다르다.
Case2. A와 B의 순열의 도형을 그리는 방향이 서로 다르다(시계방향, 반시계방향)
이 두가지 경우를 제하고 A와 순열 형태가 같아야한다.
이는 A는 고정하고 Case1를 판단하기 위해서 B의 시작점을 계속 바꿔가며, 방향도 시계방향과 반시계방향 둘다 체크하여 A와 같은지 확인한다.
위에서 시작점과 시계방향 체크를 할때 하나라도 같다면 그 문자열 B는 같은 문자열이다.
이런 문자열을 출력한다.

풀이

// baekjoon 2641 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_L=51;
const int MAX_N=101;

int N, A[MAX_L], seq, B[MAX_N][MAX_L], ans;
bool check[MAX_N];

// idx는 B 문자열의 몇 번째 문자열인지, start는 시작점이 어디인지
// dx는 1인 경우 A와 같은 방향, -1인 경우 A와 반대 방향
bool comp(int idx, int start, int dx) {
	for (int i=0; i<N; i++)
// 여기서 dx가 -1 이라면 방향을 180도 회전해 주어야 하므로 2를 더한다.
		if (A[i]%4 != (B[idx][(N+start+i*dx)%N] + ((dx < 0)? 2 : 0))%4 )
			return false;

	return true;
}

// idx는 B 문자열의 몇 번째 문자열인지, start는 시작점이 어디인지
bool comp(int idx, int start) {
	return comp(idx, start, 1) || comp(idx, start, -1);
}

int main() {
	scanf("%d", &N);
	for (int i=0; i<N; i++)
		scanf("%d", &A[i]);
	scanf("%d", &seq);
	for (int i=0; i<seq; i++)
		for (int j=0; j<N; j++)
			scanf("%d", &B[i][j]);

// A 와 B가 같은지 문자열 체크
	for (int s=0; s<seq; s++)
		for (int i=0; i<N; i++)
			if (!check[s] && comp(s, i))
				check[s]=true, ans++;

// 문자열 출력
	printf("%d\n", ans);
	for (int s=0; s<seq; s++) {
		if (check[s]) {
			for (int i=0; i<N; i++) printf("%d ", B[s][i]);
			puts("");
		}
	}
	return 0;
}