문제

안녕하세요.
백준에서 삼성 SW 역량 테스트 기출 문제집에 게시된 14891번 톱니바퀴 문제 풀이를 소개하겠습니다.

이번 문제는 톱니 바퀴를 일정 횟수 회전시켜 결과를 확인하는 문제입니다.
톱니 바퀴가 맞닿는 부분의 극이 다르면 맞닿는 톱니를 회전시키는게 가능하고, 극이 같다면 불가능 합니다. 먼저 문제를 정리하면 아래와 같습니다.

주어진 정보

  • 길이가 8인 정수 : 톱니 바퀴의 극
  • 극 값 : 0은 N, 1은 S
  • K : 명령의 수
  • 명령 : 톱니번호(n), 회전 방향(1 or -1)

해결 방향

복잡한 수를 계산하거나 탐색 알고리즘을 필요로 하지 않습니다. 단순히 조건에 맞추어 1차원 배열을 회전만 하면 되는 문제 입니다.

명령에서 선택된 톱니 바퀴를 회전 시키는 함수를 하나 작성합니다. 그리고 재귀적으로 옆의 다른 톱니 바퀴들을 작성한 함수로 회전시키면, 모든 톱니 바퀴들을 회전 시킬 수 있습니다.

주의할 점은 옆에 톱니 바퀴의 존재 여부와 톱니 바퀴의 회전 여부 입니다.


톱니 예시

톱니 바퀴 예시

풀이

풀이 코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;
/*
 * N극은 0, S극은 1
 * K : 회전 명령 갯수
 * 명령 : 톱니번호 , 방향 (1 : 시계, -1 : 반시계)
*/

vector< string > arr;
vector< vector<int> > cmd;
int K;


// 각 톱니의 12시 방향 체크
int get_score() {
	int score = 0;
	
	if (arr[1][0] == '1')	score += 1;
	if (arr[2][0] == '1')	score += 2;
	if (arr[3][0] == '1')	score += 4;
	if (arr[4][0] == '1')	score += 8;

	return score;
}

// 회전 후, 양 옆의 톱니 바퀴에 대해 재귀 진행
void rotate(int n, int wise, int prev_n) {
	bool left, right;
	left = right = true;

	if (n == 1 || n - 1 == prev_n || arr[n - 1][2] == arr[n][6]) left = false;
	if (n == 4 || n + 1 == prev_n || arr[n + 1][6] == arr[n][2]) right = false;

	// 시계 방향 회전
	if (wise == 1) {
		string tmp = arr[n].substr(7, 1);
		arr[n] = tmp + arr[n].substr(0, 7);
	}
	// 시계 반대 방향 회전
	else {
		string tmp = arr[n].substr(0, 1);
		arr[n] = arr[n].substr(1, 7) + tmp;
	}
	
	// 다음 톱니 바퀴 회전 방향 반전
	if (wise == 1) wise = -1;
	else wise = 1;
	 
	// 다음 톱니 바퀴 회전
	if (left == true) {
		rotate(n - 1, wise, n);
	}
	if (right == true) {
		rotate(n + 1, wise, n);
	}
}

int solution() {
	
	// 명령 수 만큼 회전 진행
	for (int k = 0; k < K; k++) {
		int n = cmd[k][0];		// 선택된 톱니바퀴 번호
		int wise = cmd[k][1];	// 회전 방향

		rotate(n, wise, -1);		// 회전 실행
	}

	return get_score();
}

int main() {
	arr = vector<string> (5, ""); // 1~4까지 표현하기 위해 톱니바퀴 수를 5로
	
	// 톱니바퀴 초기화
	for (int i = 1; i < 5; i++) {
		string tmp_s;
		cin >> tmp_s;
		arr[i] = tmp_s;
	}

	// 명령 수 입력
	cin >> K;
	cmd = vector<vector<int>>(K, vector<int>(2, 0)); 

	// 명령 초기화
	for (int i = 0; i < K; i++) {
		cin >> cmd[i][0];	// 톱니 번호
		cin >> cmd[i][1];	// 회전 방향
	}
	
	// 시뮬레이션 진행
	cout << solution() << endl;

	return 0;
}

해설

  • solution() : 모든 명령에 따라 회전 실행, get_socore()를 이용한 점수 계산
  • rotate() : 주어진 번호와 방향에 따라 톱니바퀴 회전
    • 양 옆의 회전 가능한 톱니가 있는지 체크
    • 현재 톱니바퀴 회전
      • ex) 1차원 배열 : [1,2,..,7,8] -> [2,3,..,8,1] or [8,1,..,6,7]
    • 회전 가능한 톱니 바퀴가 있다면 rotate() 재귀호출

앗 이걸 생각 못했네?

  • 1차원 배열 회전을 양방향으로 좀 더 간단하게 하는 방법이 없을까?
    • deque의 push, pop 활용 (1차 풀이, 아래 링크 참고)
    • 문자열 계산 활용 (현재 풀이)
  • 딱히 헷갈릴만한 부분은 없는 것 같다…

다른 풀이

14891번 톱니바퀴 1차 풀이

기타 다른 문제 풀이 코드 (github)