Min:D's Devlog

[백준][삼성 SW 역량 테스트][Silver 1][C++] 14891 톱니바퀴 본문

알고리즘/백준

[백준][삼성 SW 역량 테스트][Silver 1][C++] 14891 톱니바퀴

Min:D 2020. 9. 30. 23:35

문제

백준 삼성 SW 역량 테스트 기출 문제 - 14891 톱니바퀴 (Silver 1)

 

14891번: 톱니바퀴

첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 �

www.acmicpc.net

 


문제 풀이

접근 방식

주어진 규칙대로 톱니바퀴를 회전시킬 때, 최종 톱니바퀴의 상태를 구하는 문제이다.

한 톱니바퀴가 회전할 때 옆의 톱니바퀴와 맞닿은 톱니의 극이 다른 경우,

옆의 톱니바퀴는 반대방향으로 회전하게 된다. 이를 고려하여 톱니바퀴를 회전시켜주었다.

 

우선, 회전시킬 톱니바퀴의 주변으로 퍼져나가며 함께 회전시킬 바퀴들을 탐색을 해야하기 때문에,

BFS 함수를 만들어 탐색을 수행하였다.

이후, 시계 방향으로 회전하는 톱니바퀴는 맨 마지막의 값을 push_front한 후에 제거하고,

시계 반대 방향으로 회전하는 톱니바퀴는 맨 처음의 값을 push_back 한 후에 제거하여 회전을 구현하였다.

 


풀이 코드 - C++

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

vector<deque<int> > cogwheel(4, deque<int>(8));

void BFS(int start, int dir) {
	// 톱니바퀴가 이동할 방향 구하기
	int move[4] = { 0 };
	move[start] = dir;
	queue<pair<int,int> > q;
	q.push({ start, dir });
	while (!q.empty()) {
		int now = q.front().first;
		int dir = q.front().second;
		q.pop();
		if (now - 1 >= 0 && move[now - 1] == 0) {
			if (cogwheel[now][6] != cogwheel[now - 1][2]) {
				move[now - 1] = -dir;
				q.push({ now - 1,-dir });
			}
		}
		if (now + 1 < 4 && move[now + 1] == 0) {
			if (cogwheel[now][2] != cogwheel[now + 1][6]) {
				move[now + 1] = -dir;
				q.push({ now + 1,-dir });
			}
		}
	}

	// 톱니바퀴 이동
	for (int i = 0; i < 4; i++)	{
		if (move[i] == 1) {
			cogwheel[i].push_front(cogwheel[i][7]);
			cogwheel[i].pop_back();
		}
		else if (move[i] == -1) {
			cogwheel[i].push_back(cogwheel[i][0]);
			cogwheel[i].pop_front();
		}
	}
}

int main() {
	for (int i = 0; i < 4; i++) {
		string a;
		cin >> a;
		for (int j = 0; j < 8; j++) {
			if (a[j] == '1')
				cogwheel[i][j] = 1;
		}
	}
	int K;
	cin >> K;
	for (int i = 0; i < K; i++) {
		int a, b;
		cin >> a >> b;
		BFS(a - 1, b);
	}

	int answer = 0;
	for (int i = 0; i < 4; i++) {
		if (cogwheel[i][0] == 1)
			answer += pow(2, i);
	}
	cout << answer;
}

실행 결과

실행 결과 : 통과 (0ms)

Comments