SWEA 4013번: [모의 SW 역량테스트] 특이한 자석

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeV9sKkcoDFAVH

SW Expert Academy

 

백준에서의 톱니바퀴?와 똑같은 문제이당

 

위와 같은 그림이 있을 때, 특정 번호의 자석을 돌리면

해당 자석과 맞닿아있는 자석의 극이 다를 때 반대 방향 회전을 한다

해당 그림에서 2번 자석을 반시계방향으로 회전하면

1번 자석과는 다른 극이 맞닿아있기 때문에 1번 자석은 시계방향 회전, 

3번 자석과는 같은 극이 맞닿아있기 때문에 회전하지 않는다

해당 상태에서 3번 자석을 회전시키면 같은 원리로 2번과 4번이 회전, 1번은 2번에 의해 회전한다

 

나는 인덱스 배열을 사용해서 각 번호의 자석이 어느정도 회전해있는지 저장해주었다

예를들어 fig.3-1을 보면, 처음 상태와 비교했을 때

1번은 시계 1번 회전, 2번은 시계 1번 회전, 3번은 그대로, 4번은 그대로이기 때문에

index 배열에는 1,1,0,0이 들어가게 된다. 반시계 방향으로 회전한다면 index에 -1을 해준다

 

각 자석의 연결 상태는 그래프 형태로 전처리를 해주고, 특정 자석을 회전시킬 때 dfs를 돌리면서 회전 상태에 대한 인덱스를 변경해주면 된다!!

 

#include <cstdio>
int magnet[4][8], index[4],k,tc,ans;
bool connect[4][4] = {
	{0,1,0,0},{1,0,1,0},{0,1,0,1},{0,0,1,0}
},visit[4];
void dfs(int cur,int d) {

	for (int next = 0; next < 4; next++) {
		if ((!connect[cur][next])||visit[next])continue;
		visit[next] = 1;

		if (cur < next) {	//오른쪽 자석
			if (magnet[cur][(index[cur] + 2) % 8] != magnet[next][(index[next] - 2+8) % 8]) {
				//서로 다르면
				dfs(next, d * -1);
			}
		}
		else {
			if (magnet[cur][(index[cur] - 2 +8) % 8] != magnet[next][(index[next] + 2) % 8])
				dfs(next, d * -1);
		}
	}

	index[cur] = (index[cur] + (d * -1) + 8) % 8;	//현재 자석 회전

}
int main() {
	scanf("%d", &tc);
	for (int T = 1; T <= tc; T++) {
		ans = 0;
		scanf("%d", &k);
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 8; j++)
				scanf("%d", &magnet[i][j]);
			index[i] = 0;
		}

		int num, dir;

		for (int i = 0; i < k; i++) {
			scanf("%d%d", &num, &dir);
			for (int j = 0; j < 4; j++)visit[j] = 0;

			visit[num - 1] = 1;
			dfs(num-1, dir);
		}

		for (int i = 0,j=1; i < 4; i++,j*=2)
			ans += magnet[i][index[i]]*j;

		printf("#%d %d\n", T,ans);
		
	}
	return 0;
}