펭로그

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

Study/PS(Algorithm)

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

노랑펭귄 2018. 10. 19. 14:46

문제링크 : 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로 나눈 값을 저장해주면 된다.

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


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

15
16
1-
18
19
20
// 왼쪽(9시 방향 톱니) 좌표
int left(int idx) {
    int left = (6 + rot[idx]) % 8;
    if (left < 0) left += 8;
    return left;
}
cs



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


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

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


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

40
41
42
43
44
45
46
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);
}
cs


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

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

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

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


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

77
find(sel, dir, 1, 1);
cs


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

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

45

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



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// 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;
}
cs


<SWEA 4013 소스코드>


저작자표시

'Study > PS(Algorithm)' 카테고리의 다른 글

[C++] 백준 BOJ 16234 인구 이동  (0) 2018.10.21
[C++] 백준 BOJ 14888 연산자 끼워넣기 (SWEA 4008 숫자 만들기)  (0) 2018.10.20
[C++] 문자열 계산기  (6) 2018.10.18
[C++] 백준 BOJ 14890 경사로 (SWEA 4014 활주로 건설)  (0) 2018.10.13
[C++] 백준 BOJ 5639 이진 검색 트리  (1) 2018.10.12
'Study/PS(Algorithm)' Related Articles more
Comments