[백준][14891번] 톱니바퀴

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

14891번: 톱니바퀴

 

풀이과정

1. 현재 들어온 명령어대로 톱니바퀴의 회전이 발생한다. 이때 서로 다른 극을 가지는 주변 톱니바퀴에도 회전이 생기므로 주변 상태를 체크해야 되기 때문에 bfs를 이용했다.

 

2. 6개월전에 풀었던 소스와 비교해봤다. (재귀로 풀었다)

 

재귀로 푼게 더 깔끔한거 같다

 

소스코드 (bfs, c++)

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
enum DIR { CLOCKWISE = 1, COUNTERCLOCKWISE = -1};
using namespace std;
string gear[4];
vector<pair<int, int>> command;
int flag[4] = { 0, };
int dx[2] = { 1, -1 };
int K;
void movingGear(int num, int dir)
{
	if (dir == CLOCKWISE) {
		string tmp = gear[num].substr(0, 7);
		gear[num] = gear[num].back() + tmp;
	}
	else {
		string tmp = gear[num].substr(1, 7);
		gear[num] = tmp + gear[num].front();
	}
}
bool rotationCheck(int cur, int next)
{
	if (cur < next) {
		return gear[cur][2] != gear[next][6];
	}
	else {
		return gear[cur][6] != gear[next][2];
	}
}
void bfs(int num, int dir)
{
	queue<pair<int, int>> que;
	que.push(make_pair(num, dir));
	flag[num] = dir;
	while (!que.empty()) {
		int queSize = que.size();
		for (int i = 0; i < queSize; i++) {
			pair<int, int> p = que.front(); que.pop();
			for (int j = 0; j < 2; j++) {
				int nx = p.first + dx[j];
				if (nx < 0 || nx >= 4 || flag[nx] != 0) continue;
				if (rotationCheck(p.first, nx)) {
					int nd = (p.second == CLOCKWISE) ? COUNTERCLOCKWISE : CLOCKWISE;//next dir
					flag[nx] = nd;
					que.push(make_pair(nx, nd));
				}
			}
		}
	}
}

int solution()
{
	for (int i = 0; i < K; i++) {
		memset(flag, 0, sizeof(flag));
		int num = command[i].first;
		int dir = command[i].second;
		bfs(num, dir);
		for (int j = 0; j < 4; j++) {
			if (flag[j] == 0) continue;
			movingGear(j, flag[j]);
		}
	}
	int answer = 0;
	for (int i = 0; i < 4; i++) {
		if ((gear[i][0] - '0') == 0) continue;
		answer += (0xff & (0x01 << i));
	}
	return answer;
}

int main()
{
	for (int i = 0; i < 4; i++) {
		cin >> gear[i];
	}
	scanf("%d", &K);
	for (int i = 0; i < K; i++) {
		int n, d;
		scanf("%d %d", &n, &d);
		command.push_back(make_pair(n - 1, d));
	}
	printf("%d\n", solution());
}

 

소스코드 (재귀)

#include <stdio.h>
#include <string.h>

int map[4][8];
int visited[4];
int N;

void moveMap(int idx, int d)
{
	int _map[8];
	if (d == 1) { //right
		memcpy(_map+1, map[idx], sizeof(map[idx]) - sizeof(map[idx][0]));
		_map[0] = map[idx][7];
		memcpy(map[idx], _map, sizeof(map[idx]));
	}
	else { // left
		memcpy(_map, map[idx]+1, sizeof(map[idx]) - sizeof(map[idx][0]));
		_map[7] = map[idx][0];
		memcpy(map[idx], _map, sizeof(map[idx]));
	}
}

void solution(int n, int d)
{
	int m1 = 0, m2 = 0;
	visited[n] = 1;
	if (n + 1 < 4 && visited[n +1] == 0) {
		if (map[n][2] != map[n + 1][6]) {
			solution(n + 1, d == 1 ? -1 : 1);
		}
	}
	if (n - 1 >= 0 && visited[n-1] == 0) {
		if (map[n][6] != map[n - 1][2]) {
			solution(n - 1, d == 1 ? -1 : 1);
		}
	}
	moveMap(n, d);

}

int main()
{
	for (int i = 0; i < 4; i++)
	{
		char str[9];
		scanf("%s", str);
		for (int j = 0; j < 8; j++) {
			map[i][j] = str[j] - '0';
		}
	}
	// 1 시계 -1 반시계
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int n, d;
		scanf("%d %d", &n, &d);
		memset(visited, 0, sizeof(visited));
		solution(n-1, d);
	}
	int answer = 0;
	for (int i = 0; i < 4; i++) {
		if (map[i][0] == 1) {
			answer += (1 << i);
		}
	}
	printf("%d\n", answer);
}

 

결과