[C++] 백준 BOJ 14891 톱니바퀴 (SWEA 4013 특이한 자석)

문제링크 : https://noj.am/14891

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeV9sKkcoDFAVH

<백준 14891 기준 문제 풀이>

톱니바퀴가 회전하게 되면 각각의 인덱스 위치가 변동된다.

어떤 톱니바퀴의 인덱스가 다음과 같다면

0 1 2 3 4 5 6 7

시계방향으로 회전시

7 1 2 3 4 5 6

반시계방향으로 회전시

1 2 3 4 5 6 0

이렇게 순서가 바뀌므로 rot[] 에 회전이 얼마나 되었는지를 저장해준다.

8바퀴를 회전하게 되면 제자리가 되므로 8로 나눈 값을 저장해주면 된다.

// 톱니바퀴 회전
void rotat(int idx, int dir) {
    rot[idx] = (rot[idx] - dir) % 8;
}

회전시 바뀐 좌표를 가져오는 경우는 다음과 같이 구성했다.

// 왼쪽(9시 방향 톱니) 좌표
int left(int idx) {
    int left = (6 + rot[idx]) % 8;
    if (left < 0) left += 8;
    return left;
}

문제에서 톱니바퀴가 회전을 하게 되었을 경우

[좌측 톱니바퀴의 3시 방향] 과 [현재 톱니바퀴의 9시 방향]이 서로 다를 경우 좌측 톱니바퀴가 회전을 하게 되고

[현재 톱니바퀴의 3시 방향] 과 [우측 톱니바퀴의 9시 방향]이 서로 다른 경우 우측 톱니바퀴가 회전을 하게 된다.

따라서, 다음과 같이 재귀적으로 좌/우측 탐색을 시행해주면 된다.

if (chkL && prev >= 1) {
    int l = gear[prev][right(prev)]; // 좌측 톱니의 3시
    int r = gear[cur][left(cur)]; // 현재 톱니의 9시
    // 좌측 톱니와 서로 극이 다르면 좌측 탐색
    if (l != r)
        find(prev, -dir, 1, 0);
}

맨 처음 톱니바퀴 회전시 - 좌측과 우측의 톱니바퀴가 회전을 하는지 체크를 해야하기 때문에

find( ) 함수를 다음과 같이 구성했다.

chkL과 chkR을 통하여 좌/우측 톱니바퀴를 체크하며

void find(int cur, int dir, bool chkL, bool chkR)

첫 시행에서는 chkL = 1, chkR = 1로 좌/우측을 모두 탐색하며

find(sel, dir, 1, 1);

좌측 톱니바퀴를 재귀적으로 탐색할 때는 chkL = 1, chkR = 0으로 재귀적으로 탐색하고

우측 톱니바퀴를 재귀적으로 탐색할 때는 chkL = 0, chkR = 1으로 재귀적으로 탐색한다.

find(prev, -dir, 1, 0);
 
find(next, -dir, 0, 1);

// BOJ_14891 톱니바퀴
#include <iostream>
#include <cmath>
 
using namespace std;
 
char gear[5][8]; // 톱니바퀴
int rot[5]; // 회전수
 
// 톱니바퀴 회전
void rotat(int idx, int dir) {
    rot[idx] = (rot[idx] - dir) % 8;
}
 
// 왼쪽(9시 방향 톱니) 좌표
int left(int idx) {
    int left = (6 + rot[idx]) % 8;
    if (left < 0) left += 8;
    return left;
}
 
// 오른쪽(3시 방향 톱니) 좌표
int right(int idx) {
    int right = (2 + rot[idx]) % 8;
    if (right < 0) right += 8;
    return right;
}
 
// 맨위(12시 방향 톱니) 좌표
int top(int idx) {
    int top = 0 + rot[idx];
    if (top < 0) top += 8;
    return top;
}
 
void find(int cur, int dir, bool chkL, bool chkR) {
    int prev = cur - 1; // 좌측 톱니 인덱스
    int next = cur + 1; // 우측 톱니 인덱스
    // 좌측 톱니 찾기
    if (chkL && prev >= 1) {
        int l = gear[prev][right(prev)]; // 좌측 톱니의 3시
        int r = gear[cur][left(cur)]; // 현재 톱니의 9시
        // 좌측 톱니와 서로 극이 다르면 좌측 탐색
        if (l != r)
            find(prev, -dir, 1, 0);
    }
    // 우측 톱니 찾기
    if (chkR && next <= 4) {
        int l = gear[cur][right(cur)]; // 현재 톱니의 3시
        int r = gear[next][left(next)]; // 우측 톱니의 9시
        // 우측 톱니와 서로 극이 다르면
        if (l != r)
            find(next, -dir, 0, 1);
    }
 
    rotat(cur, dir); // 회전 ㄱㄱ
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
    // N극 0 / S극 1
    // 오른쪽 [2] 왼쪽 [6]
 
    for (int i = 1; i <= 4; i++)
        cin >> gear[i];
 
    int N;
    cin >> N;
    while (N--) {
        int sel; // 몇번째 톱니?
        int dir; // 시계 1 / 반시계 -1
        cin >> sel >> dir;
 
        find(sel, dir, 1, 1);
    }
 
    int result = 0;
    for (int i = 1; i <= 4; i++)
        if (gear[i][top(i)] == '1')
            result += pow(2, i - 1);
 
    cout << result;
 
    return 0;
}

<SWEA 4013 소스코드>

// SWEA_4013 특이한 자석
#include <iostream>
#include <cmath>
 
using namespace std;
 
char gear[5][8]; // 톱니바퀴
int rot[5]; // 회전수
 
// 톱니바퀴 회전
void rotat(int idx, int dir) {
    rot[idx] = (rot[idx] - dir) % 8;
}
 
// 왼쪽(9시 방향 톱니) 좌표
int left(int idx) {
    int left = (6 + rot[idx]) % 8;
    if (left < 0) left += 8;
    return left;
}
 
// 오른쪽(3시 방향 톱니) 좌표
int right(int idx) {
    int right = (2 + rot[idx]) % 8;
    if (right < 0) right += 8;
    return right;
}
 
// 맨위(12시 방향 톱니) 좌표
int top(int idx) {
    int top = 0 + rot[idx];
    if (top < 0) top += 8;
    return top;
}
 
void find(int cur, int dir, bool chkL, bool chkR) {
    int prev = cur - 1; // 좌측 톱니 인덱스
    int next = cur + 1; // 우측 톱니 인덱스
    // 좌측 톱니 찾기
    if (chkL && prev >= 1) {
        int l = gear[prev][right(prev)]; // 좌측 톱니의 3시
        int r = gear[cur][left(cur)]; // 현재 톱니의 9시
        // 좌측 톱니와 서로 극이 다르면 좌측 탐색
        if (l != r)
            find(prev, -dir, 1, 0);
    }
    // 우측 톱니 찾기
    if (chkR && next <= 4) {
        int l = gear[cur][right(cur)]; // 현재 톱니의 3시
        int r = gear[next][left(next)]; // 우측 톱니의 9시
        // 우측 톱니와 서로 극이 다르면
        if (l != r)
            find(next, -dir, 0, 1);
    }
 
    rotat(cur, dir); // 회전 ㄱㄱ
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int tc;
    cin >> tc;
    for (int T = 1; T <= tc; T++) {
        int N;
        cin >> N;
        
        for (int i = 1; i <= 4; i++)
            for (int j = 0; j < 8; j++)
                cin >> gear[i][j];
        for (int i = 1; i <= 4; i++)
            rot[i] = 0;
 
        while (N--) {
            int sel; // 몇번째 톱니?
            int dir; // 시계 1 / 반시계 -1
            cin >> sel >> dir;
 
            find(sel, dir, 1, 1);
        }
 
        int result = 0;
        for (int i = 1; i <= 4; i++)
            if (gear[i][top(i)] == '1')
                result += pow(2, i - 1);
 
        cout << "#" << T << " " << result << "\n";
    }
 
    return 0;
}