[PS] 백준 15662번 톱니바퀴 (2)

박상혁·2026년 7월 31일

PS

목록 보기

92/108

이번에는 백준 15662번 톱니바퀴 (2) 문제를 풀어보았습니다.

하나의 톱니바퀴를 회전시키면 맞닿아 있는 톱니의 극에 따라 양옆의 톱니바퀴도 연쇄적으로 회전할 수 있습니다.

따라서 각 회전 명령마다 영향을 받는 톱니바퀴를 재귀적으로 탐색하고, 서로 반대 방향으로 회전시키는 방식으로 해결하였습니다.

문제 설명

8개의 톱니를 가진 톱니바퀴 T개가 일렬로 놓여 있습니다.

각 톱니는 다음 두 극 중 하나를 나타냅니다.

N극: 0
S극: 1

특정 톱니바퀴를 회전시킬 때, 인접한 톱니바퀴와 맞닿아 있는 극이 서로 다르면 인접한 톱니바퀴도 반대 방향으로 회전합니다.

이 영향은 다음 톱니바퀴로 계속 전달될 수 있습니다.

주어진 K번의 회전을 모두 수행한 뒤, 12시 방향의 톱니가 S극인 톱니바퀴의 개수를 구하는 문제입니다.

풀이 아이디어

각 톱니바퀴의 상태를 길이가 8인 문자열로 저장하였습니다.

vector<string> inp;

문자열의 각 인덱스는 다음 위치를 의미합니다.

0번 인덱스: 12시 방향
2번 인덱스: 오른쪽 톱니바퀴와 맞닿는 부분
6번 인덱스: 왼쪽 톱니바퀴와 맞닿는 부분

현재 톱니바퀴와 오른쪽 톱니바퀴가 서로 영향을 주는 조건은 다음과 같습니다.

inp[num][2] != inp[num+1][6]

현재 톱니바퀴와 왼쪽 톱니바퀴가 서로 영향을 주는 조건은 다음과 같습니다.

inp[num-1][2] != inp[num][6]

맞닿은 극이 다르면 인접한 톱니바퀴는 현재 방향과 반대 방향으로 회전해야 하므로 !vec을 전달하여 재귀 호출합니다.

같은 톱니바퀴를 다시 탐색하는 것을 막기 위해 used 배열을 사용하였습니다.

코드

#include <bits/stdc++.h>
using namespace std;
int T;
bool used[1000];
vector<string> inp;
vector<pair<int, int>> inp_act;
void act_rotate(int num, bool vec) {
    string tmp;
    tmp.resize(8);

    if(vec) {
        for (int i=0; i<8; i++) {
            tmp[(i+1) % 8] = inp[num][i];
        }
    } else {
        for (int i=0; i<8; i++) {
            tmp[(i+7) % 8] = inp[num][i];
        }
    }
    inp[num] = tmp;
}
void rotate_topni(int num, bool vec) {
    if (T == 1) {
        act_rotate(num,vec);
        return;
    }
    if (num == 0) {
        if (!used[num+1] && (inp[num][2] != inp[num+1][6])) {
            used[num+1] = true;
            rotate_topni(num+1, !vec);
        }
    } else if (num == T-1) {
        if (!used[num-1] && (inp[num-1][2] != inp[num][6])) {
            used[num-1] = true;
            rotate_topni(num-1, !vec);
        }
    } else {
        if (!used[num+1] && (inp[num][2] != inp[num+1][6])) {
            used[num+1] = true;
            rotate_topni(num+1, !vec);
        }

        if (!used[num-1] && (inp[num-1][2] != inp[num][6])) {
            used[num-1] = true;
            rotate_topni(num-1, !vec);
        }
    }
    act_rotate(num,vec);
}
int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> T;
    for (int i=0; i<T; i++) {
        string tmp;
        cin >> tmp;
        inp.push_back(tmp);
    }
    int n;
    cin >> n;
    for (int i=0; i<n; i++) {
        int num, vec;
        cin >> num >> vec;
        inp_act.push_back({num-1, vec});
    }

    for (pair<int, int> act : inp_act) {
        memset(used, false, sizeof(used));
        used[act.first] = true;
        rotate_topni(act.first, act.second==1);
    }

    int ret = 0;
    for (int i=0; i<T; i++) {
        if (inp[i][0] == '1') ret++;
    }

    cout << ret;
    return 0;
}

풀이 흐름

각 톱니바퀴의 8개 극 상태를 문자열로 입력받습니다.
회전시킬 톱니바퀴 번호와 방향을 저장합니다.
하나의 회전 명령을 실행하기 전에 used 배열을 초기화합니다.
처음 회전시키는 톱니바퀴를 방문 처리합니다.
현재 톱니바퀴와 오른쪽 톱니바퀴의 맞닿은 극을 비교합니다.
극이 다르면 오른쪽 톱니바퀴를 반대 방향으로 재귀 호출합니다.
현재 톱니바퀴와 왼쪽 톱니바퀴도 같은 방식으로 확인합니다.
영향을 받는 톱니바퀴를 모두 탐색한 뒤 현재 톱니바퀴를 회전시킵니다.
모든 회전 명령을 수행한 후 각 톱니바퀴의 12시 방향을 확인합니다.
12시 방향이 S극인 톱니바퀴의 개수를 출력합니다.

구현 포인트

1. 톱니바퀴 상태를 문자열로 저장

vector<string> inp;

각 톱니바퀴는 8개의 극을 가지고 있으므로 길이가 8인 문자열로 표현할 수 있습니다.

예를 들어 다음 문자열은 하나의 톱니바퀴 상태를 의미합니다.

10101111

문제에서 12시 방향부터 시계 방향으로 상태가 주어지므로 문자열의 인덱스와 톱니 위치가 바로 대응됩니다.

2. 맞닿은 톱니의 인덱스

톱니바퀴 두 개가 맞닿는 부분은 다음 인덱스입니다.

왼쪽 톱니바퀴의 2번 인덱스
오른쪽 톱니바퀴의 6번 인덱스

따라서 현재 톱니바퀴와 오른쪽 톱니바퀴를 비교할 때는 다음 조건을 사용합니다.

inp[num][2] != inp[num+1][6]

극이 서로 다르면 오른쪽 톱니바퀴도 회전합니다.

왼쪽 톱니바퀴와 비교할 때는 다음 조건을 사용합니다.

inp[num-1][2] != inp[num][6]

왼쪽 톱니바퀴의 오른쪽 극과 현재 톱니바퀴의 왼쪽 극을 비교하는 것입니다.

3. 시계 방향 회전

if(vec) {
    for (int i=0; i<8; i++) {
        tmp[(i+1) % 8] = inp[num][i];
    }
}

vec이 true라면 시계 방향 회전을 의미합니다.

시계 방향으로 한 칸 회전하면 기존 i번 위치의 값이 i + 1번 위치로 이동합니다.

마지막 인덱스인 7번은 다시 0번으로 이동해야 하므로 % 8을 사용합니다.

기존 0번 → 새로운 1번
기존 1번 → 새로운 2번
...
기존 7번 → 새로운 0번

4. 반시계 방향 회전

else {
    for (int i=0; i<8; i++) {
        tmp[(i+7) % 8] = inp[num][i];
    }
}

반시계 방향으로 한 칸 회전하면 기존 i번 위치의 값이 i - 1번 위치로 이동합니다.

인덱스가 음수가 되는 것을 방지하기 위해 8에서 1을 뺀 7을 더한 뒤 % 8을 사용합니다.

기존 0번 → 새로운 7번
기존 1번 → 새로운 0번
기존 2번 → 새로운 1번

회전 결과는 임시 문자열 tmp에 저장한 후 원본 톱니바퀴에 대입합니다.

inp[num] = tmp;

5. 재귀적으로 회전 영향 전파

void rotate_topni(int num, bool vec)

num은 현재 회전할 톱니바퀴의 번호이고, vec은 회전 방향을 나타냅니다.

현재 톱니바퀴가 회전하면 양옆의 톱니바퀴가 영향을 받는지 확인합니다.

맞닿은 극이 다르면 인접한 톱니바퀴도 회전해야 합니다.

rotate_topni(num+1, !vec);

인접한 톱니바퀴는 현재 톱니바퀴와 반대 방향으로 회전하므로 !vec을 전달합니다.

6. 반대 방향 전달

현재 톱니바퀴가 시계 방향으로 회전하면 인접한 톱니바퀴는 반시계 방향으로 회전합니다.

반대로 현재 톱니바퀴가 반시계 방향이면 인접한 톱니바퀴는 시계 방향으로 회전합니다.

코드에서는 회전 방향을 bool로 표현하였습니다.

true: 시계 방향
false: 반시계 방향

따라서 다음과 같이 논리 부정 연산자를 사용하면 반대 방향을 전달할 수 있습니다.

!vec

7. `used` 배열을 사용하는 이유

bool used[1000];

톱니바퀴의 회전 영향은 양쪽 방향으로 전달됩니다.

예를 들어 2번 톱니바퀴가 3번 톱니바퀴를 회전시킨 뒤, 3번 톱니바퀴가 다시 2번 톱니바퀴를 확인할 수 있습니다.

방문 처리가 없다면 다음과 같이 서로를 계속 재귀 호출할 수 있습니다.

2번 → 3번 → 2번 → 3번 → ...

이를 방지하기 위해 이미 확인한 톱니바퀴는 used 배열에 표시합니다.

if (!used[num+1] && ...)

아직 방문하지 않은 톱니바퀴만 재귀 호출합니다.

8. 회전 명령마다 방문 배열 초기화

for (pair<int, int> act : inp_act) {
    memset(used, false, sizeof(used));

used 배열은 하나의 회전 명령에서 중복 탐색을 방지하기 위한 용도입니다.

다음 회전 명령에서는 모든 톱니바퀴를 다시 확인할 수 있어야 하므로 매번 false로 초기화합니다.

처음 회전시키는 톱니바퀴는 바로 방문 처리합니다.

used[act.first] = true;

이후 해당 톱니바퀴에서부터 연쇄 회전을 시작합니다.

rotate_topni(act.first, act.second==1);

9. 양 끝 톱니바퀴 처리

가장 왼쪽 톱니바퀴는 오른쪽 이웃만 존재합니다.

if (num == 0) {
    if (!used[num+1] && (inp[num][2] != inp[num+1][6])) {

가장 오른쪽 톱니바퀴는 왼쪽 이웃만 존재합니다.

else if (num == T-1) {
    if (!used[num-1] && (inp[num-1][2] != inp[num][6])) {

중간에 있는 톱니바퀴는 양쪽을 모두 확인합니다.

else {

이를 통해 배열 범위를 벗어난 톱니바퀴에 접근하지 않도록 처리하였습니다.

10. 톱니바퀴가 하나인 경우

if (T == 1) {
    act_rotate(num,vec);
    return;
}

톱니바퀴가 하나뿐이라면 인접한 톱니바퀴가 존재하지 않습니다.

따라서 다른 톱니바퀴와 극을 비교하지 않고 현재 톱니바퀴만 회전시킨 뒤 함수를 종료합니다.

11. 실제 회전을 마지막에 수행하는 이유

act_rotate(num,vec);

현재 톱니바퀴의 실제 회전은 인접한 톱니바퀴에 대한 재귀 호출이 끝난 뒤 수행합니다.

맞닿은 극의 비교는 모든 톱니바퀴가 회전하기 전 상태를 기준으로 이루어져야 합니다.

현재 톱니바퀴를 먼저 회전시켜버리면 2번, 6번 인덱스의 값이 달라져 인접 톱니바퀴의 회전 여부를 잘못 판단할 수 있습니다.

따라서 다음 순서로 처리합니다.

인접한 극 비교
→ 영향을 받는 톱니바퀴 재귀 호출
→ 현재 톱니바퀴 실제 회전

재귀 호출된 톱니바퀴들도 같은 구조로 동작하므로, 모든 회전 여부를 기존 상태를 기준으로 판단할 수 있습니다.

12. 입력된 회전 방향 변환

문제에서는 다음과 같이 방향이 주어집니다.

1: 시계 방향
-1: 반시계 방향

코드의 act_rotate() 함수에서는 방향을 bool로 받습니다.

true: 시계 방향
false: 반시계 방향

따라서 다음 비교 결과를 전달합니다.

act.second==1

입력 방향이 1이면 true, -1이면 false가 됩니다.

13. 최종 결과 계산

모든 회전 명령을 수행한 뒤 각 톱니바퀴의 12시 방향을 확인합니다.

for (int i=0; i<T; i++) {
    if (inp[i][0] == '1') ret++;
}

문자열의 0번 인덱스가 12시 방향입니다.

값이 '1'이면 S극이므로 정답을 1 증가시킵니다.

시간복잡도

회전 명령 하나가 실행될 때 최악의 경우 모든 톱니바퀴에 회전 영향이 전달될 수 있습니다.

각 톱니바퀴를 회전시키는 데는 길이가 8인 문자열을 순회하므로 상수 시간이 필요합니다.

따라서 회전 명령 하나의 시간복잡도는 다음과 같습니다.

O(T)

회전 명령은 총 K번 주어지므로 전체 시간복잡도는 다음과 같습니다.

O(K × T)

T와 K는 각각 최대 1,000이므로 충분히 해결할 수 있습니다.

박상혁

엉덩이로 성장하는 개발자

이전 포스트

[PS] 백준 17406번 배열 돌리기 4

다음 포스트

[PS] 백준 15662번 톱니바퀴 (2)

PS

문제 설명

풀이 아이디어

코드

풀이 흐름

구현 포인트

1. 톱니바퀴 상태를 문자열로 저장

2. 맞닿은 톱니의 인덱스

3. 시계 방향 회전

4. 반시계 방향 회전

5. 재귀적으로 회전 영향 전파

6. 반대 방향 전달

7. `used` 배열을 사용하는 이유

8. 회전 명령마다 방문 배열 초기화

9. 양 끝 톱니바퀴 처리

10. 톱니바퀴가 하나인 경우

11. 실제 회전을 마지막에 수행하는 이유

12. 입력된 회전 방향 변환

13. 최종 결과 계산

시간복잡도

[PS] 백준 17406번 배열 돌리기 4

[PS] 백준 1911번 흙길 보수하기

0개의 댓글

[PS] 백준 15662번 톱니바퀴 (2)

PS

문제 설명

풀이 아이디어

코드

풀이 흐름

구현 포인트

1. 톱니바퀴 상태를 문자열로 저장

2. 맞닿은 톱니의 인덱스

3. 시계 방향 회전

4. 반시계 방향 회전

5. 재귀적으로 회전 영향 전파

6. 반대 방향 전달

7. used 배열을 사용하는 이유

8. 회전 명령마다 방문 배열 초기화

9. 양 끝 톱니바퀴 처리

10. 톱니바퀴가 하나인 경우

11. 실제 회전을 마지막에 수행하는 이유

12. 입력된 회전 방향 변환

13. 최종 결과 계산

시간복잡도

[PS] 백준 17406번 배열 돌리기 4

[PS] 백준 1911번 흙길 보수하기

0개의 댓글

7. `used` 배열을 사용하는 이유