백준 14891 톱니바퀴 C 풀이 - Brute Force

 

 

 

톱니바퀴를 빙글빙글 돌리는 문제이다.

 

문제의 조건은 다음 하나 뿐이다.

1. 특정 번호의 톱니바퀴를 돌릴 때, 바로 옆에 맞닿아있는 톱니바퀴와 다른 극으로 마주볼 때 같이 돌아간다.

 

주의해야할 점은 다음과 같다.

1. 1번 톱니바퀴를 돌렸을 때 4번 톱니바퀴까지 돌아갈 수 있다.

2. 1번 톱니바퀴를 돌렸을 때, 2번 톱니바퀴가 돌아가지 않으면 3번 톱니바퀴는 당연히 돌아가지 않는다.

3. 위, 오른쪽, 왼쪽 방향을 인덱스를 통해 가리키는 방법을 사용할 경우 돌리는 방향과 반대로 인덱스가 움직여야 한다.

ex) 오른쪽으로 돌림 -> 위,오른쪽, 왼쪽 인덱스는 왼쪽으로 이동(-1) 

3번은 다른 방법을 썼을 시 이해하기 어려우므로 코드를 참고하면 좋다.

 

문제 해결방식은 다음과 같다.

1. 톱니바퀴를 자석 상태와 위, 왼쪽, 오른쪽을 가리키는 인덱스의 구조체 배열로 선언한다. (M magnet[5])

2. 돌려야하는 톱니바퀴의 번호와 방향을 입력받아서 주변에 돌아갈 수 있는 톱니바퀴들을 찾는다.

3. 모두 찾았다면 한 번에 상태를 바꾼다. (먼저 바꾸면 안됨)

4. 다음 입력을 받고 2-3을 반복한다.

 

 

 

 

전체코드

#include <stdio.h>
int K;
#define N 0 //N극
#define S 1 //S극

//톱니바퀴 구조체
typedef struct st {
	int top, left, right;
	int Magnet[9];
}M;
M magnet[5];
//거듭제곱
int pow(int x, int n) {
	int ret = 1;
	for (int i = 0; i < n; i++) {
		ret *= x;
	}
	return ret;
}
//위쪽에 S극 있는 톱니바퀴 점수 계산
int check() {
	int ret = 0;
	for (int i = 1; i <= 4; i++) {
		if (magnet[i].Magnet[magnet[i].top] == S) {
			ret += pow(2, i-1);
		}
	}
	return ret;
}
//톱니바퀴 번호(idx)와 방향 (dir)을 받아서 top,left,right 인덱스 변경
//1~8범위안에 들어와야하므로 넘어갈경우 -8 0보다 작아질경우 +8을 해준다.
//주의할 점은 돌리는 방향과 반대로 가야한다는 점이다.
void turning(int idx, int dir) {
	magnet[idx].top = magnet[idx].top - dir + (magnet[idx].top-dir <= 0 ? 8 : 0) + (magnet[idx].top-dir >=9?-8:0);
	magnet[idx].left = magnet[idx].left - dir + (magnet[idx].left-dir <= 0 ? 8 : 0)+ (magnet[idx].left - dir >= 9 ? -8 : 0);
	magnet[idx].right = magnet[idx].right - dir + (magnet[idx].right-dir <= 0 ? 8 : 0)+ (magnet[idx].right - dir >= 9 ? -8 : 0);
	//printf("#[%d] %d %d %d\n",idx, magnet[idx].top, magnet[idx].left, magnet[idx].right);
}
//dir -1 왼쪽
//돌릴 수 있는 톱니바퀴들 전부 찾기
void move(int idx, int dir) {
	int turn[5] = { 0 };
	turn[idx] = dir;
	int l = idx - 1, r = idx + 1;
    //왼쪽방향 톱니바퀴중 돌아갈 수 있는 것 찾기
	while (l > 0) {
    //SN 이 마주보고 있을 때만 돌아감
		if (magnet[l +1].Magnet[magnet[l + 1].left] !=
			magnet[l].Magnet[magnet[l].right]) {
			turn[l] = -turn[l + 1];
		}
        //3번을 돌릴 경우 2번이 돌아가지 않는다면 1번도 당연히 안돌아가므로 종료
		else {
			break;
		}
		l--;
	}
    //오른쪽방향
	while (r <= 4) {
		if (magnet[r - 1].Magnet[magnet[r - 1].right] !=
			magnet[r].Magnet[magnet[r].left]) {
			turn[r] = -turn[r - 1];
		}
		else {
			break;
		}
		r++;
	}
	//돌아갈 수 있는 톱니바퀴와 돌리는 방향 저장한 turn 배열
	for (int i = 1; i <= 4; i++) {
		if (turn[i]) {
			turning(i, turn[i]);
		}
	}
	return ;
}

int main() {
	for (int i = 1; i <= 4; i++) {
    //초기 인덱스 설정
		magnet[i].top = 1;
		magnet[i].right = 3;
		magnet[i].left = 7;
		for (int j = 1; j <= 8; j++) {
			scanf("%1d", &magnet[i].Magnet[j]);
		}
	}
	scanf("%d", &K);
	int n, d;
	for (int i = 0; i < K; i++) {
		scanf("%d %d", &n, &d);
        //입력과 동시에 수행
		move(n, d);
	}
	printf("%d\n", check());
}