<Baekjoon> #14891 Deque_톱니바퀴 c++
처음에 문제를 보고 쉬운 문제라고 생각했고
톱니바퀴의 상태를 저장하는 벡터를 만들고 옆에 있는 톱니와 맞닿는 톱니의 index
를 따로 저장해서 톱니가 움직일 때마다 이 index
만 계속 변경해주면 된다고 생각했다.
그런데 그럴 필요 없이 deque
를 이용하면 훨씬 편하게 구할 수 있다.
(톱니바퀴의 원형 구조를 그림에 떡하니 그려놓은 거는deque
를 사용하라고 그런 것 같다.. 눈치 못 챈 나는 바보)
톱니바퀴를 돌릴 때 비교해야 하는 값은
왼쪽 톱니의 3번째와 가운데 톱니의 7번째 톱니, 가운데 톱니의 3번째와 오른쪽 톱니의 7번째 톱니를 차례대로 비교해가야 한다는 것을 알고 시작한다.
deque
생성 및 저장
- 4개의 deque를 만들고 입력 값을 저장한다
deque<int> dq[4];
- 현재 톱니와 양쪽의 톱니 비교
solution (int idx, int dir)
함수에서는 현재 톱니의index
와 방향(dir)
을 받아와 양쪽 톱니와 비교한다- 하나의 톱니를 돌리면 그 옆에 톱니들의
N,S
극을 비교하여 연쇄적으로 돌려야하기 때문에 톱니를 더이상 돌리지 않아도 될 때까지 반복한다.- 이때 반드시
visited
로 이미 이 지점을 방문했고 톱니가 돌아갈 것이라는 표시를 해준다.3번
톱니가시계 방향
이면2번
톱니는시계 반대 방향
,1번
톱니는시계 방향
이렇게 움직여야 하기 때문에 방향을 매번 바꿔준다(dir*(-1))
visited[idx] = true; int Lidx = idx - 1; int Ridx = idx + 1; if (Lidx >= 0 && !visited[Lidx] && dq[Lidx][2] != dq[idx][6]) solution(idx - 1, dir * (-1)); if (Ridx < 4 && !visited[Ridx] && dq[idx][2] != dq[Ridx][6]) solution(idx + 1, dir * (-1));
- 톱니를 돌려야 하는 양 끝단의 톱니부터 돌려준다
- 시계 반대방향으로 돌리는 경우 톱니의 제일 상단
dq[].front()
의 값이 제일 마지막으로 간다.
if (dir == -1) { int tmp = dq[idx].front(); dq[idx].pop_front(); dq[idx].push_back(tmp); }
- 시계 방향으로 돌리는 경우 톱니의 제일 하단
dq[].back()
의 값이 제일 앞으로 간다.
else if (dir == 1) { int tmp = dq[idx].back(); dq[idx].pop_back(); dq[idx].push_front(tmp); }
전체 코드
#include <iostream> #include <deque> #include <algorithm> using namespace std; deque<int> dq[4]; bool visited[4]; void init() { for (int i = 0; i < 4; i++) { string c; cin >> c; for (int j = 0; j < 8; j++) { int tmp = c[j]-'0'; dq[i].push_back(tmp); } } } void turnCog(int idx, int dir) { if (dir == -1) { int tmp = dq[idx].front(); dq[idx].pop_front(); dq[idx].push_back(tmp); } else if (dir == 1) { int tmp = dq[idx].back(); dq[idx].pop_back(); dq[idx].push_front(tmp); } } void solution(int idx, int dir) { visited[idx] = true; int Lidx = idx - 1; int Ridx = idx + 1; if (Lidx >= 0 && !visited[Lidx] && dq[Lidx][2] != dq[idx][6]) solution(idx - 1, dir * (-1)); if (Ridx < 4 && !visited[Ridx] && dq[idx][2] != dq[Ridx][6]) solution(idx + 1, dir * (-1)); turnCog(idx, dir); } int main() { init(); int testCase; cin >> testCase; while (testCase--) { int idx, dir; cin >> idx >> dir; solution(idx - 1, dir); memset(visited, false, sizeof(visited)); } int answer = 0; for (int i = 0; i < 4; i++) { if (dq[i][0]) answer += pow(2, i); } cout << answer << endl; return 0; }
Author And Source
이 문제에 관하여(<Baekjoon> #14891 Deque_톱니바퀴 c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Baekjoon-14891-Deque톱니바퀴-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)