Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- Gold 4
- 월간 코드 챌린지
- SWEA
- 부스트코스
- 백준
- Level 2
- Level 4
- pass
- 코드 리뷰
- 시뮬레이션
- 백트래킹
- 구현
- Gold 5
- 2020 카카오 인턴십
- DFS
- Web
- 코드리뷰
- Level 3
- BFS
- c++
- DP
- 프로그래머스
- 삼성 SW 역량 테스트
- 2020 KAKAO BLIND
- 그리디
- level 1
- 스택/큐
- 브루트포스
- next_permutation
- 2019 KAKAO BLIND
Archives
- Today
- Total
Min:D's Devlog
[백준][삼성 SW 역량 테스트][Silver 1][C++] 14891 톱니바퀴 본문
문제
백준 삼성 SW 역량 테스트 기출 문제 - 14891 톱니바퀴 (Silver 1)
문제 풀이
접근 방식
주어진 규칙대로 톱니바퀴를 회전시킬 때, 최종 톱니바퀴의 상태를 구하는 문제이다.
한 톱니바퀴가 회전할 때 옆의 톱니바퀴와 맞닿은 톱니의 극이 다른 경우,
옆의 톱니바퀴는 반대방향으로 회전하게 된다. 이를 고려하여 톱니바퀴를 회전시켜주었다.
우선, 회전시킬 톱니바퀴의 주변으로 퍼져나가며 함께 회전시킬 바퀴들을 탐색을 해야하기 때문에,
BFS 함수를 만들어 탐색을 수행하였다.
이후, 시계 방향으로 회전하는 톱니바퀴는 맨 마지막의 값을 push_front한 후에 제거하고,
시계 반대 방향으로 회전하는 톱니바퀴는 맨 처음의 값을 push_back 한 후에 제거하여 회전을 구현하였다.
풀이 코드 - C++
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
vector<deque<int> > cogwheel(4, deque<int>(8));
void BFS(int start, int dir) {
// 톱니바퀴가 이동할 방향 구하기
int move[4] = { 0 };
move[start] = dir;
queue<pair<int,int> > q;
q.push({ start, dir });
while (!q.empty()) {
int now = q.front().first;
int dir = q.front().second;
q.pop();
if (now - 1 >= 0 && move[now - 1] == 0) {
if (cogwheel[now][6] != cogwheel[now - 1][2]) {
move[now - 1] = -dir;
q.push({ now - 1,-dir });
}
}
if (now + 1 < 4 && move[now + 1] == 0) {
if (cogwheel[now][2] != cogwheel[now + 1][6]) {
move[now + 1] = -dir;
q.push({ now + 1,-dir });
}
}
}
// 톱니바퀴 이동
for (int i = 0; i < 4; i++) {
if (move[i] == 1) {
cogwheel[i].push_front(cogwheel[i][7]);
cogwheel[i].pop_back();
}
else if (move[i] == -1) {
cogwheel[i].push_back(cogwheel[i][0]);
cogwheel[i].pop_front();
}
}
}
int main() {
for (int i = 0; i < 4; i++) {
string a;
cin >> a;
for (int j = 0; j < 8; j++) {
if (a[j] == '1')
cogwheel[i][j] = 1;
}
}
int K;
cin >> K;
for (int i = 0; i < K; i++) {
int a, b;
cin >> a >> b;
BFS(a - 1, b);
}
int answer = 0;
for (int i = 0; i < 4; i++) {
if (cogwheel[i][0] == 1)
answer += pow(2, i);
}
cout << answer;
}
실행 결과
'알고리즘 > 백준' 카테고리의 다른 글
[백준][삼성 SW 역량 테스트][Gold 5][C++] 14503 로봇 청소기 (0) | 2020.10.02 |
---|---|
[백준][삼성 SW 역량 테스트][Silver 3][C++] 14889 스타트와 링크 (0) | 2020.10.01 |
[백준][삼성 SW 역량 테스트][Gold 4][C++] 15685 드래곤 커브 (0) | 2020.09.29 |
[백준][삼성 SW 역량 테스트][Gold 5][C++] 15684 사다리 조작 (0) | 2020.09.28 |
[백준][삼성 SW 역량 테스트][Gold 5][C++] 15686 치킨 배달 (0) | 2020.09.26 |
Comments