BOJ: 톱니바퀴(2)(15662) [C++]

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

15662번: 톱니바퀴 (2)

 

고민을 길게 해봤으나 결국 마감일까지 풀지 못하고 제출실패, ,

실패한 주된 이유는 각 톱니바퀴의 회전 체크 여부(아래 코드에서 visited 배열)를 표시해주지 않았기 때문이었다.

회전여부는 회전당 한 번만 결정된다. 그리고 톱니바퀴가 돌아가는 데는 순서가 없다.

체크 여부를 표시해주지 않으면 이미 돌린 톱니에 의해 극을 다시 체크하여 실제 회전 상태와 다른 동작이 일어나는 문제가 발생한다. 이 때문에 테케가 뭐는 되고 뭐는 안 되고 했던 듯

사실 중복체크를 해야한다는 발상자체는 했으나... bool 자료형으로 처리해보려 했다가 실패

 

인접한 톱니를 확인할 때, 왼쪽으로 인접한 것과 오른쪽으로 인접한 것에서 각 동작이 다른 것에 유의

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

using namespace std;

vector<string> li; //톱니바퀴를 저장
//li[0] : 1번째 톱니바퀴, li[1]: 2번째 톱니바퀴, ...

vector<pair<int, int>> stack; //돌려야하는 톱니바퀴 인덱스와 방향
vector<int>visited; //검사한 톱니바퀴를 다시 검사하면 올바르지 않은 결과가 나오므로 검사여부 표시

void check_rotation(int current_num, int current_dir) {
	//매개변수: 현재 기준이 되는 바퀴의 인덱스와 회전 방향

	//왼쪽에 있는 톱니바퀴가 회전하는지 검사
	if (current_num - 1 >= 0 && visited[current_num - 1] == 0) { //왼쪽에 톱니바퀴가 있고, 아직 검사하지 않은 상태여야 회전가능
		//나의 6번째 톱니와 내 왼쪽의 2번째 톱니 비교
		if (li[current_num][6] != li[current_num-1][2]) { //맞물린 톱니가 다른 극이면 회전해야 함
			stack.push_back(make_pair(current_num - 1, current_dir * -1)); //왼쪽 톱니바퀴를 반대 방향으로 회전
			visited[current_num - 1] = 1; //검사했음을 표시
			check_rotation(current_num - 1, current_dir * -1); //왼쪽 톱니바퀴에 대해 재귀호출
		}
	}
	//오른쪽에 있는 톱니바퀴가 회전하는지 검사
	if (current_num + 1  < li.size() && visited[current_num + 1] == 0) { //오른쪽에 톱니바퀴가 있고, 아직 검사하지 않은 상태여야 회전가능
		//나의 2번째 톱니와 내 왼쪽의 6번째 톱니 비교
		if (li[current_num][2] != li[current_num+1][6]) { //맞물린 톱니가 다른 극이면 회전해야 함
			stack.push_back(make_pair(current_num + 1, current_dir * -1)); //오른쪽 톱니바퀴를 반대 방향으로 회전
			visited[current_num + 1] = 1; //검사했음을 표시
			check_rotation(current_num + 1, current_dir * -1); //오른쪽 톱니바퀴에 대해 재귀호출
		}
	}
}

int main() {
	int t; //톱니바퀴의 개수
	cin >> t;
	li.resize(t); //t만큼 li 할당
	for (int i = 0; i < t; i++) { //톱니바퀴 정보 입력받음
		cin >> li[i];
	}
	int k; //회전횟수
	cin >> k;
	for (int i = 0; i < k; i++) { //첫번째로 돌려야 할 톱니바퀴에 대해 바로 돌리기
		int num, direction; //회전한 톱니바퀴 인덱스, 방향
		cin >> num >> direction;
		stack.clear(); //매 회전마다 새로 받아야 하므로 스택 초기화
		stack.push_back(make_pair(num - 1, direction)); //회전 정보를 저장. 톱니바퀴 인덱스는 톱니바퀴번호 - 1
		visited.assign(t, 0); //방문 여부 표시를 위한 배열 할당
		visited[num - 1] = 1; //첫번째 톱니바퀴에 방문 표시
		
		//돌릴 톱니바퀴 체크
		check_rotation(num - 1, direction);

		//돌려야 하는 톱니바퀴를 모두 체크한 이후
		while (!stack.empty()) {
			pair<int, int> top = stack.back(); //회전 정보를 스택에서 꺼냄
			stack.pop_back(); //스택에서 삭제
			int tmp_num = top.first; //현재 돌려야 할 톱니바퀴 인덱스
			int tmp_dir = top.second; //현재 돌려야할 톱니바퀴 방향
			if (tmp_dir == 1) { //시계방향이면
				li[tmp_num] = li[tmp_num].back() + li[tmp_num].substr(0, 7); //맨 뒤였던 것을 맨 앞으로 하고 나머지 붙이기
			}
			else { //반시계 방향이면
				li[tmp_num] = li[tmp_num].substr(1) + li[tmp_num][0]; //1번째~7번째 인덱스를 맨앞으로 옮기고 0번째 인덱스를 맨 뒤로 붙이기
			}
		}
	}
	//12시 방향(0번인덱스)이 S극인 톱니바퀴 개수 세기
	int cnt = 0;
	for (int i = 0; i < t; i++) {
		if (li[i][0] == '1') {
			cnt++;
		}
	}
	cout << cnt;
	return 0;
}

 

반복문을 사용해 각 회전마다 로직을 적용해준다.

회전 정보 입력받고, visited를 초기화해준 뒤 회전 여부를 체크하는 함수를 실행한다.

체크가 끝나면 실제로 돌려줘야 하니까 while문을 실행. 이때 stack 배열에는 회전이 결정된 톱니바퀴의 정보가 들어있다.

그 정보들을 꺼내서 각 톱니바퀴를 맞는 방향으로 돌려주면 된다.