문제 분석
- BFS를 이용하면 깔끔하게 풀이 할 수 있다. 문제를 읽어 가면서 BFS를 써야겠다는 생각은 했지만 구현을 하면서 잔 실수가 많아서 구현을 하는데 시간이 오래 걸렸다.
- 톱니바퀴를 회전시킬때 어떤 톱니바퀴를 돌릴지 정한다음에 한번에 다같이 돌려야 한다. 처음에 문제를 제대로 읽지 않고 그냥 풀어서 이점을 놓쳐서 시간을 지체 하게 되었다.
시간 복잡도
BFS : 4 ( queue에 4개의 톱니가 모두 들어갈 경우 )
Rotation : 16 x 4
( 1 개의 톱니를 회전 시키는데 8번 queue에 넣고 다시 8번 배열에 넣어야 한다. )
K의 갯수 : 최대 100 회
전체 시간 복잡도 : 100 x ( ( 16 x 4 ) + 4 )
구현
시계 방향 및 반시계 방향 회전
반복문을 사용해서 구현 할 수도 있지만 개인적으로 그게 더 헷갈려서 queue를 이용해서 문제를 해결했다.
코드만 보면 아마 이해가 잘 가지 않을 수도 있다.
우선 dir 값은 1 또는 -1을 가진다. 1인 경우 시계 방향으로 회전해야 하고 -1인경우 반시계 방향으로 회전해야 한다.
말이 시계 반시계 회전이지 그냥 오른쪽으로 한칸씩 미냐 왼쪽으로 한칸씩 미냐의 차이다.
그림으로 이해하자면 다음과 같다.
Modulo를 이용하면 다음과 같이 순환적 형태로 배열에 접근 할 수 있다.
BFS
-
일반적인 BFS랑 그냥 아예 똑같다!! 2차원이나 1차원 배열에서 BFS를 구현해본 경험이 한번이라도 있다면 그 방식과 굉장히 유사 한 것을 바로 알 수 있을 것이다.
-
인덱스가 0-3을 벗어나는지 확인한다.!! ( 바퀴는 4개이기 때문이다. )
-
이미 회전한 바퀴에 대해서는 BFS를 하지 않는다.
-
인접한 톱니 바퀴들 중에서 현재 바퀴와 다른 극이 맞닿아 있는 바퀴들에 대해서만 BFS를 한다.
-
BFS를 할 때 현재 방향과 반대 방향으로 나중에 모아서 회전 시켜 주기 위해서 현재 톱니 바퀴의 회전 방향과 반대 방향으로 Rotation 배열에 넣어준다.
왼쪽과 오른쪽 맞닿은 부분 확인 ( very bad !! )
- 내가 짰지만 이런 식으로 함수를 작성하는것은 별로 좋지 못한것 같다. 내가 짰지만 내가 너무 헷갈렸다.
차라리
is_connected ( int 톱니 바퀴 번호, int 방향 )
이런식으로 함수를 구성하고 결과 값으로 같은 극과 연결되어 있는지 여부를 반환하는 형태로 짜는 것이 훨씬 직관적이고 좋은 형태의 함수였을 것 같다.
헤맸던 부분
- is_connected() 함수를 그지같이 짜서 너무 헷갈렸다.
- continue 함수를 잘못 사용해서 BFS에서 왼쪽 / 오른쪽을 모두 확인해야 하는데
while(!tq.empty()){
int cur_tn = tq.front(); tq.pop();
int left = cur_tn - 1;
int right = cur_tn + 1;
if( 왼쪽 BFS 안해도 됨 ) continue;
if( 오른쪽 BFS 안해도 됨 ) continue;
}이런식으로 코드를 작성해서 왼쪽을 확인하다가 continue가 나면 오른쪽도 아예 확인을 못해서 이 문제를 잡는데 오래 걸렸다.
얻은 것
1. BFS의 복습
2. Modulo의 복습
전체 코드 [ 내 코드 ]
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void init(){
ios::sync_with_stdio(0);
cin.tie(0);
}
string Tn[5];
vector<pair<int,int> > cases;
int N;
void get_input(){
for(int i = 0 ; i < 4; i++) cin >> Tn[i];
cin >> N;
for(int i = 0 ; i < N; i++){
int start;
int state;
cin >> start >> state;
cases.push_back(make_pair(start - 1, state));
}
}
void clean_rotation(){
for(int i = 0 ; i < 5; i++) Rotation[i] = 0;
}
void rotate(int num, int dir){
if(dir == 0) return;
queue<int> tq;
int start;
if(dir == 1) start = 7;
else start = 1;
for(int i = 0 ; i < 8; i++)
tq.push(Tn[num][(start + i) % 8]);
for(int i = 0 ; i < 8 ; i ++)
Tn[num][i] = tq.front();
tq.pop();
}
int is_connected(int left, int right){
// 극이 다르면 1을 반환
// 극이 같으면 0을 반환
if(Tn[left][2] != Tn[right][6]) return 1;
return 0;
}
int pow(int p){
int start = 1;
if(p == 0) return 1;
for(int i = 0 ; i < p; i++){
start *= 2;
}
return start;
}
int get_score(){
int score = 0;
for(int i = 0 ; i < 4 ; i++){
if(Tn[i][0] == '1') {
score += pow(i);
}
}
return score;
}
int Rotation[5];
void bfs(int start, int rot_dir){
clean_rotation(); // Rotation 배열을 모두 0으로 초기화 한다.
queue<int> tq;
tq.push(start);
Rotation[start] = rot_dir;
// BFS를 시작
while(!tq.empty()){
int cur_tn = tq.front(); tq.pop();
int dir[2] = {-1,1};
// 좌우의 방향에 대하여
for(int i = 0 ; i < 2; i++){
int n_dir = cur_tn + dir[i];
if(n_dir < 0 || n_dir >= 4) continue;
if(Rotation[n_dir] != 0) continue;
if( dir[i] == 1 // 방향이 오른쪽인 경우
&& is_connected(cur_tn, n_dir)){
// 오른쪽 방향과 극이 다른지 확인
Rotation[n_dir] = -Rotation[cur_tn];
tq.push(n_dir);
}
if( dir[i] == -1 // 방향이 왼쪽이 경우
&& is_connected(n_dir, cur_tn)){
// 왼쪽 방향과 극이 다른지 확인.
Rotation[n_dir] = -Rotation[cur_tn];
tq.push(n_dir);
}
}
}
}
void rotate_all(){
for(int i = 0 ; i < 4; i++)
rotate(i, Rotation[i]);
}
int main(void){
init();
get_input();
for(int i = 0 ; i < cases.size(); i++){
bfs(cases[i].first, cases[i].second);
rotate_all();
}
cout << get_score() << "\n";
return 0;
}
// 문제에 나온 케이스 이걸 돌려 보면서 디버깅 하는 것을 추천!! //
/**
10101111
01111101
11001110
00000010
2
3 -1
1 1
**/
}느낀점
- 3시간 2솔은 도대체 어떻게 하는걸까...
