SWEA 4013번 [모의 SW 역량테스트] 특이한 자석 C++ 덱, 재귀

리뷰

 

SWEA를 풀면서 처음으로 만난 덱을 써서 푸는 문제

SW Expert Academy

 

문제 풀이

tc를 입력 받고 각 테스트 케이스를 개행한다, 이후 init, input, solution 함수를 실행하고 각 테케마다 ans를 출력해줬다.

1. init()

ans를 0으로 초기화 해주고 각 자석 정보를 clear를 통해 초기화 해준다.

2. input()

k값을 받아와 주고, 4개의 자석에 각각 N극과 S극 정보를 받아와 준다.

3. solution()

k번을 순회하며 회전시킬 자석과 방향정보를 입력 받고 각 자석을 돌려준다.

자석을 돌리기 전에 방문배열 초기화와 회전시킬 자석의 방문처리가 필요하다.

4.bt(int index, int dir)

1. 재귀를 통해 자석을 회전시키는 시뮬레이션을 구현한다.
2. 매개변수 index는 현재 자석의 번호이고, dir은 회전시킬 방향의 정보이다.
3. 우선 회전시키기 전에 옆 좌석과 인접해 있는 부분을 먼저 확인해 주어야 한다.
4. 자신보다 왼쪽에 있는 자석의 경우 현재 자석의 6번 인덱스와 왼쪽 자석의 2번 인덱스를 비교해 준다.
5. 만약 두 자석의 극이 다르다면 index - 1, dir * -1로 왼쪽 자석을 방향을 반대로 돌려 재귀를 실행해 준다.
6. 오른쪽에 있는 자석의 경우 현재 자석의 2번 인덱스와 오른쪽 자석의 6번 인덱스를 비교해 준다.
7. 만약 두 자석의 극이 다르다면 index + 1, dir * 1로 오른쪽 자석을 방향을 반대로 돌려 재귀를 실행해 준다.
8. 위 작업을 해줄때에는 반드시 해당 인덱스에 방문처리를 해주어야 한다.
9. 이후 만약 dir이 1이라면 오른쪽으로 회전, dir이 -1이라면 왼쪽으로 회전시켜 준다.

 

참고 사항

k를 실행할 때마다 점수를 갱신해 주는게 아닌 k번 회전을 모두 시킨 후에 0번 인덱스의 극에 해당하는 점수를 합산한다.

 

정답 코드

#include<iostream>
#include<deque>
#include<cstring>
#include<cmath>

using namespace std;

int tc, k, ans;
deque<int> mag[5];
int v[5];

void init() {
	ans = 0;
	for (int i = 0; i < 5; i++) mag[i].clear();
}

void input() {
	cin >> k;
	for (int i = 1; i <= 4; i++) {
		for (int j = 0; j < 8; j++) {
			int a; cin >> a;
			mag[i].push_back({ a });
		}
	}
}

void bt(int index, int dir) {
	if (1 < index && !v[index - 1]) {
		v[index - 1] = 1;
		if (mag[index - 1][2] != mag[index][6]) {
			bt(index - 1, dir * -1);
		}
	}
	if (index < 4 && !v[index + 1]) {
		v[index + 1] = 1;
		if (mag[index][2] != mag[index + 1][6]) {
			bt(index + 1, dir * -1);
		}
	}
	if (dir == 1) {
		mag[index].push_front(mag[index].back());
		mag[index].pop_back();
	}
	else  {
		mag[index].push_back(mag[index].front());
		mag[index].pop_front();
	}
}

void solution() {
	for (int i = 0; i < k; i++) {
		int a, b; cin >> a >> b;
		memset(v, 0, sizeof(v));
		v[a] = 1;
		bt(a, b);
	}
	for (int i = 1; i <= 4; i++) {
		ans += mag[i].front() * pow(2, i - 1);
	}
}

int main() {
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		init();
		input();
		solution();
		cout << "#" << t << " " << ans << "\n";
	}
}