C - [백준 14891] 톱니바퀴 (feat. 시뮬레이션)

참고 포스트

 

 

 

 

 

BOJ_14891_톱니바퀴(https://www.acmicpc.net/problem/14891)

 

백준 14891번 "톱니바퀴" 문제는 4개의 톱니바퀴가 주어졌을 때, 주어진 회전 명령에 따라 톱니바퀴들의 상태를 구하는 시뮬레이션 문제입니다. 톱니바퀴는 각각 8개의 톱니로 이루어져 있으며, 시계 방향 또는 반시계 방향으로 회전합니다.

 

문제 조건

1. 각 톱니바퀴는 8개의 톱니를 가지고 있으며, 톱니의 극(N극 또는 S극)이 주어집니다.
2. 톱니바퀴의 회전 규칙:
   • 두 톱니바퀴가 맞닿은 극이 서로 다르면 반대 방향으로 회전합니다.
   • 극이 같으면 회전하지 않습니다.
3. 주어진 회전 명령에 따라 톱니바퀴들을 회전시킨 후, 각 톱니바퀴의 상태에 따라 점수를 계산합니다.

 

입력 형식

1. 첫 번째 줄부터 네 줄에는 각 톱니바퀴의 초기 상태(8자리 2진수)가 주어집니다.
   • 0은 N극, 1은 S극을 의미합니다.
2. 다음 줄에는 회전 횟수 K가 주어집니다.
3. 그다음 K개의 줄에는 두 개의 정수 (a, b)가 주어집니다.
   • a: 회전시킬 톱니바퀴 번호 (1~4)
   • b: 회전 방향 (1은 시계 방향, -1은 반시계 방향)

 

출력 형식

• 톱니바퀴의 최종 상태에 따라 계산한 점수를 출력합니다.

---

Checkpoint

이 문제는 시뮬레이션과 연쇄적인 상태 변화를 다루는 문제입니다. 다른 언어에서는 deque 같은 라이브러리를 활용하여 톱니바퀴 회전을 처리하는 경우가 많지만, C언어에서는 이러한 라이브러리가 제공되지 않으므로 배열과 플래그를 활용해 직접 구현해야 했습니다.

코드에서는 다음과 같은 방식으로 배열과 플래그를 활용하여 문제를 해결했습니다:

---

1. 배열과 인덱스를 활용한 회전 처리

톱니바퀴의 상태를 나타내는 배열 cogwheels와 12시 방향 인덱스를 관리하는 currents 배열을 사용해 회전을 처리했습니다.

int cogwheels[4][8];    // 4개의 톱니바퀴 상태 저장
int currents[4] = {0};  // 각 톱니바퀴의 12시 방향 인덱스

톱니바퀴를 회전시킬 때, 실제로 배열의 값을 이동시키지 않고 currents 인덱스를 변경하여 간단히 구현했습니다.

• 시계 방향:

  currents[num] = (currents[num] + 7) % 8;
  

• 반시계 방향:

  currents[num] = (currents[num] + 1) % 8;
  

---

2. 인접 톱니바퀴와의 극 비교

각 톱니바퀴의 **왼쪽 톱니(6번)**와 **오른쪽 톱니(2번)**를 비교하여 회전 전파를 처리합니다.
이를 위해 모듈러 연산을 사용하여 원형 배열 구조를 관리했습니다:

• 현재 톱니의 왼쪽 극:

  int left = cogwheels[num1][(currents[num1] + 6) % 8];
  

• 현재 톱니의 오른쪽 극:

  int right = cogwheels[num1][(currents[num1] + 2) % 8];
  

이와 같이 배열의 실제 데이터를 이동시키지 않고 인덱스만을 활용해 톱니의 상태를 참조하므로 메모리 효율성과 연산 속도를 모두 향상시킬 수 있었습니다.

---

3. 회전 전파

인접 톱니바퀴로 회전을 전파할 때, 플래그 배열(rotations)을 활용해 각 톱니바퀴의 회전 방향을 기록했습니다.
이 과정에서 조건문을 사용해 왼쪽과 오른쪽으로 전파를 구분했습니다:

• 왼쪽으로 전파:
• if (0 <= num1 - 1 && left != cogwheels[num1 - 1][(currents[num1 - 1] + 2) % 8]) { rotation(num1 - 1, -num2, flag - 1); }
• 오른쪽으로 전파:
• if (num1 + 1 < 4 && right != cogwheels[num1 + 1][(currents[num1 + 1] + 6) % 8]) { rotation(num1 + 1, -num2, flag + 1); }

---

구현 코드

#include <stdio.h>

int cogwheels[4][8];
int currents[4] = {0};
int K;

void rotation(int num1, int num2, int flag) {
    int left = cogwheels[num1][(currents[num1] + 6) % 8];  // 현재 톱니바퀴의 왼쪽 톱니
    int right = cogwheels[num1][(currents[num1] + 2) % 8]; // 현재 톱니바퀴의 오른쪽 톱니

    // 회전 전파
    if (flag == 0) {
        // 왼쪽 비교
        if (0 <= num1 - 1 && left != cogwheels[num1 - 1][(currents[num1 - 1] + 2) % 8]) {
            rotation(num1 - 1, -num2, flag - 1);
        }
        // 오른쪽 비교
        if (num1 + 1 < 4 && right != cogwheels[num1 + 1][(currents[num1 + 1] + 6) % 8]) {
            rotation(num1 + 1, -num2, flag + 1);
        }
    } else if (flag < 0) {
        // 왼쪽 비교
        if (0 <= num1 - 1 && left != cogwheels[num1 - 1][(currents[num1 - 1] + 2) % 8]) {
            rotation(num1 - 1, -num2, flag - 1);
        }
    } else if (flag > 0) {
        // 오른쪽 비교
        if (num1 + 1 < 4 && right != cogwheels[num1 + 1][(currents[num1 + 1] + 6) % 8]) {
            rotation(num1 + 1, -num2, flag + 1);
        }
    }

    // 회전 전파가 완료된 후에 currents 업데이트
    if (num2 == 1) { // 시계 방향
        currents[num1] = (currents[num1] + 7) % 8;
    } else if (num2 == -1) { // 반시계 방향
        currents[num1] = (currents[num1] + 1) % 8;
    }
}

int main() {
    // 톱니바퀴 상태 입력
    for (int i = 0; i < 4; i++) {
        char temp[9];
        scanf("%s", temp);
        for (int j = 0; j < 8; j++) {
            cogwheels[i][j] = temp[j] - '0';
        }
    }

    // 회전 명령 입력
    scanf("%d", &K);
    for (int i = 0; i < K; i++) {
        int num1, num2;
        scanf("%d %d", &num1, &num2);
        rotation(num1 - 1, num2, 0); // 톱니바퀴 번호는 0부터 시작
    }

    // 점수 계산
    int score = 0;
    for (int i = 0; i < 4; i++) {
        if (cogwheels[i][currents[i]] == 1) {
            score += (1 << i);
        }
    }
    printf("%d\n", score);

    return 0;
}

 

---

주요 구조 및 변수

1. cogwheels:
   • 각 톱니바퀴의 상태를 저장하는 2차원 배열입니다.
   • cogwheels[i][j]: i번째 톱니바퀴의 j번째 톱니를 나타냅니다.
2. currents:
   • 각 톱니바퀴의 12시 방향 위치를 관리하는 배열입니다.
   • 톱니가 회전할 때, 배열의 값을 직접 이동시키는 대신, 12시 방향 인덱스만 업데이트합니다.
3. K:
   • 회전 명령의 개수를 저장합니다.
4. rotation 함수:
   • 톱니바퀴를 회전시키고, 인접 톱니바퀴가 회전해야 하는 경우를 처리합니다.

---

코드 흐름

1. 톱니바퀴 상태 입력

• 4개의 톱니바퀴 상태를 문자열로 입력받아, 각 문자를 정수로 변환하여 cogwheels 배열에 저장합니다.

for (int i = 0; i < 4; i++) {
    char temp[9];
    scanf("%s", temp);
    for (int j = 0; j < 8; j++) {
        cogwheels[i][j] = temp[j] - '0';
    }
}

---

2. 회전 명령 입력 및 처리

• K개의 회전 명령을 입력받아 rotation 함수를 호출합니다.
• 회전할 톱니바퀴 번호(num1)와 회전 방향(num2)이 주어지며, 톱니바퀴 번호는 1부터 시작하지만 배열 인덱스는 0부터 시작하기 때문에 num1 - 1로 변환합니다.

scanf("%d", &K);
for (int i = 0; i < K; i++) {
    int num1, num2;
    scanf("%d %d", &num1, &num2);
    rotation(num1 - 1, num2, 0);
}

---

3. 회전 함수 (rotation)

• 입력 인자:
  • num1: 회전할 톱니바퀴 번호 (0~3)
  • num2: 회전 방향 (1: 시계 방향, -1: 반시계 방향)
  • flag: 회전 전파 방향 제어를 위한 플래그 (0: 양방향, <0: 왼쪽, >0: 오른쪽)
• 동작 과정:
  1. 현재 톱니바퀴의 왼쪽/오른쪽 톱니 확인:
     • 왼쪽 톱니: (currents[num1] + 6) % 8
     • 오른쪽 톱니: (currents[num1] + 2) % 8
  2. 왼쪽/오른쪽 톱니와 극 비교:
     • 왼쪽 톱니바퀴와 오른쪽 톱니바퀴의 극이 다르면, 해당 톱니바퀴를 반대 방향으로 회전하도록 재귀 호출.
  3. 현재 톱니바퀴의 회전:
     • currents 배열을 업데이트하여 12시 방향의 위치를 갱신합니다.

void rotation(int num1, int num2, int flag) {
    int left = cogwheels[num1][(currents[num1] + 6) % 8];  // 현재 톱니바퀴의 왼쪽 톱니
    int right = cogwheels[num1][(currents[num1] + 2) % 8]; // 현재 톱니바퀴의 오른쪽 톱니

    // 회전 전파
    if (flag == 0) {
        // 왼쪽 비교
        if (0 <= num1 - 1 && left != cogwheels[num1 - 1][(currents[num1 - 1] + 2) % 8]) {
            rotation(num1 - 1, -num2, flag - 1);
        }
        // 오른쪽 비교
        if (num1 + 1 < 4 && right != cogwheels[num1 + 1][(currents[num1 + 1] + 6) % 8]) {
            rotation(num1 + 1, -num2, flag + 1);
        }
    } else if (flag < 0) {
        // 왼쪽 비교
        if (0 <= num1 - 1 && left != cogwheels[num1 - 1][(currents[num1 - 1] + 2) % 8]) {
            rotation(num1 - 1, -num2, flag - 1);
        }
    } else if (flag > 0) {
        // 오른쪽 비교
        if (num1 + 1 < 4 && right != cogwheels[num1 + 1][(currents[num1 + 1] + 6) % 8]) {
            rotation(num1 + 1, -num2, flag + 1);
        }
    }

    // 회전 전파가 완료된 후에 currents 업데이트
    if (num2 == 1) { // 시계 방향
        currents[num1] = (currents[num1] + 7) % 8;
    } else if (num2 == -1) { // 반시계 방향
        currents[num1] = (currents[num1] + 1) % 8;
    }
}

---

4. 점수 계산

• 톱니바퀴의 12시 방향의 값을 기준으로 점수를 계산합니다.
• 각 톱니바퀴의 점수는 2^i(i는 톱니바퀴 번호)로 계산됩니다.

int score = 0;
for (int i = 0; i < 4; i++) {
    if (cogwheels[i][currents[i]] == 1) {
        score += (1 << i);
    }
}
printf("%d\n", score);

---

실행 흐름 요약

1. 입력 처리:
   • 톱니바퀴 상태와 회전 명령을 입력받습니다.
2. 회전 처리:
   • 각 명령마다 rotation 함수를 호출해 회전 시뮬레이션을 실행합니다.
3. 점수 계산:
   • 최종적으로 각 톱니바퀴의 상태를 기반으로 점수를 계산합니다.

---

 

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.