[백준] 14891번: 톱니바퀴

https://www.acmicpc.net/problem/14891

14891번: 톱니바퀴

 

문제 이해

예전에 SWEA에서 푼 문제랑 동일하다.

그래서 그리 어렵지 않게 풀 수 있었다.

문제를 제대로 읽으면 되는데, 사실 한 번 풀어봤던 문제라고 대충 읽었다가 오타를 엄청 내고 말았다.

 

일단

1. 톱니바퀴 a가 돌면 a+1 이나 a-1 은 반대방향으로 돈다

2. 극성이 다를 때 따라 돈다. 

 

이 두 개를 살짝 헷갈렸다.

 

톱니바퀴는 친절하게 4개밖에 안주어진다. 그리고 날도 8개밖에 없다.

그러니까 그냥 4*8 의 이차원 배열로 만들어주면 된다.

 

톱니바퀴를 돌리는 부분은 재귀함수를 이용해줬다.

톱니바퀴를 돌리려고 할때,

오른쪽에 톱니바퀴가 돌아가야 하면 오른쪽 톱니바퀴를 먼저 돌린다.

왼쪽에 톱니바퀴가 돌아가야 하면 왼쪽 톱니바퀴를 먼저 돌린다.

이제 이 톱니바퀴를 돌린다.

 

여기서 주의할 부분은, 이렇게 하다보면 재귀가 미친듯이 일어난다.

3번을 돌릴 때 4번이 같이 돌아간다 -> 4번에서 돌리면서 왼쪽 확인하니, 얘도 돌아갈 애다 -> 3번 돌리러 간다 -> 4번 또 돌리러 간다.....

 

그러므로, 이미 돌린 것이라고 표시하기 위해 turned라는 배열을 도입했다.

근데 여기서 처음 돌릴 애가 3번이면 turned[3] = 1 을 먼저하고 4번 톱니바퀴 (함수 호출)를 돌려야 한다. 처음에 함수 맨 끝에다가 turned[no] = 1 했다가 위와 같은 무한재귀가 일어났다... (난 멍청이라 넣어봐야 아나보다 ^^)

 

이것들만 주의하면 문제될 것이 없다!

 

최종 코드

#include <stdio.h>
#include <string.h>
#define NORTH 0
#define SOUTH 1
#define RIGHT 1
#define LEFT -1
#define MAXK 100

int K;
int gear[4+2][8+2];
int cmd[MAXK][2]; // 번호, 방향 
int turned[4 + 2]; // 한 판 당 돌렸으면 무시

void Get_Input(void) {
	for (int i = 1; i <= 4; i++) {
		for(int j = 0; j<8; j++){
			scanf("%1d", &gear[i][j]);
		}
	}
	scanf("%d", &K);
	for (int i = 0; i < K; i++) {
		scanf("%d %d", &cmd[i][0], &cmd[i][1]);
	}
}

void Turn_Gear(int no, int dir) {
	
	turned[no] = 1;
	// 오른쪽에 톱니바퀴 있는 경우
	if (no+1 <=4){		
		if (gear[no][2] != gear[no + 1][6]) {
			// 오른쪽 돌려야 함
			if (turned[no + 1] != 1) {
				Turn_Gear(no + 1, (-1)*dir);
			}
		}
	}
	// 왼쪽에 톱니바퀴 있는 경우
	if (no - 1 >= 1) {
		if (gear[no][6] != gear[no - 1][2]) {
			// 왼쪽도 돌려야함
			if (turned[no - 1] != 1) {
				Turn_Gear(no - 1, (-1) * dir);
			}
		}
	}
	// 본인 돌기
	if (dir == RIGHT) {
		// 오른쪽으로 돌기
		int tmp = gear[no][7];
		for (int i = 7; i > 0; i--) {
			gear[no][i] = gear[no][i - 1];
		}
		gear[no][0] = tmp;
	}
	else {
		// 왼쪽으로 돌기
		int tmp = gear[no][0];
		for (int i = 0; i < 7; i++) {
			gear[no][i] = gear[no][i + 1];
		}
		gear[no][7] = tmp;
	}
	
}

int Get_Answer(void) {
	int ans = 0;
	if (gear[1][0] == SOUTH) ans += 1;
	if (gear[2][0] == SOUTH) ans += 2;
	if (gear[3][0] == SOUTH) ans += 4;
	if (gear[4][0] == SOUTH) ans += 8;
	return ans;
}

int main(void) {
	Get_Input();
	for (int i = 0; i < K; i++) {
		memset(turned, 0, sizeof(turned));
		Turn_Gear(cmd[i][0], cmd[i][1]);
	}
	printf("%d", Get_Answer());
	return 0;
}