[SWEA] 4013 특이한 자석 - JAVA

1. 문제

BOJ 14891 톱니바퀴와 동일하다.

SW Expert Academy

14891번: 톱니바퀴

총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.

이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다.

톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다. 예를 들어, 아래와 같은 경우를 살펴보자.

두 톱니바퀴의 맞닿은 부분은 초록색 점선으로 묶여있는 부분이다. 여기서, 3번 톱니바퀴를 반시계 방향으로 회전했다면, 4번 톱니바퀴는 시계 방향으로 회전하게 된다. 2번 톱니바퀴는 맞닿은 부분이 S극으로 서로 같기 때문에, 회전하지 않게 되고, 1번 톱니바퀴는 2번이 회전하지 않았기 때문에, 회전하지 않게 된다. 따라서, 아래 그림과 같은 모양을 만들게 된다.

위와 같은 상태에서 1번 톱니바퀴를 시계 방향으로 회전시키면, 2번 톱니바퀴가 반시계 방향으로 회전하게 되고, 2번이 회전하기 때문에, 3번도 동시에 시계 방향으로 회전하게 된다. 4번은 3번이 회전하지만, 맞닿은 극이 같기 때문에 회전하지 않는다. 따라서, 아래와 같은 상태가 된다.

톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.

---

2. 풀이

static 변수들

static int[][] magnet = new int[4][8];
static int[] idx = new int[4];
static boolean[] visited;

 

입력 및 자석 돌리는 함수 호출

자석 정보를 magnet에 저장하고, 맨 위에 있는 자석 인덱스를 idx배열에 따로 저장한다. 테스트 케이스가 하나라면 처음에 idx를 입력하지 않아도 되지만, 테스트 케이스가 여러 개 있기 때문에 0을 저장한다.

자석을 한 번 돌릴 때마다 visited 배열을 초기화한다. 한 회차에만 여러번 돌리지 않으면 되기 때문이다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(in.readLine());
StringTokenizer st;
StringBuilder sb = new StringBuilder();

for(int tc=1;tc<=T;tc++){
   int K = Integer.parseInt(in.readLine());
   for(int i=0;i<4;i++){
      st = new StringTokenizer(in.readLine());
      for(int j=0;j<8;j++){
         magnet[i][j] = Integer.parseInt(st.nextToken());
      }
      idx[i] = 0;
   }

   for(int k=0;k<K;k++){
      st = new StringTokenizer(in.readLine());
      visited = new boolean[4];
      turn(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken()));
   }

 

자석 돌리기

1.  방문한 적 있는 자석이라면 빠져나간다. 그렇지 않다면 방문배열을 true로 바꾼다.

2.  가장 위의 인덱스는 idx에 저장돼있다(top). 

3.  옆의 오른쪽 자석과 맞닿은 자석은 top+6에서 %8연산을 했다. top-2를 해야 하는데, 그렇게 되면 정해진 인덱스 범위에서 벗어날 위험이 있기 때문에 top+8-2=top+6을 했다.

4.  옆의 왼쪽 자석과 맞닿은 자석은 top+2를 했다. 이 인덱스도 배열 범위에서 벗어날 수 있기 때문에 %연산을 했다.

5.  왼쪽 자석이 있다면(num>0) 왼쪽 자석과 현재 자석 종류를 확인한다. 왼쪽자석의 오른쪽 톱니바퀴이므로 현재 자석에서 right계산하는 방식과 똑같이 한다.

6.  오른쪽 자석이 있다면(num<3) 오른쪽 자석과 현재 자석 종류를 확인한다. 오른쪽 자석의 왼쪽 톱니바퀴이므로 현재 자석에서 left 계산하는 방식과 같다.

7.  5~6번에서, 현재 방향과 반대방향으로 돌려야하므로 -way를 넣어서 돌린다.

8.  새로운 꼭대기 톱니바퀴 인덱스를 설정한다. 꼭대기 톱니바퀴는 자석이 도는 반대방향으로 움직인다. 따라서 (top+8-way)%8을 한다. +8을 하는 건 마이너스 인덱스를 막기위해서, %8을 하는 건 인덱스가 넘치는걸 막기 위해서다.

private static void turn(int num, int way) {
   if(visited[num]) return;
   visited[num] = true;

   int top = idx[num];
   int left = (top+6)%8;
   int right = (top+2)%8;

   if(num>0){
      if(magnet[num-1][(idx[num-1]+2)%8]!=magnet[num][left]) turn(num-1,-way);
   }

   if(num<3){
      if(magnet[num+1][(idx[num+1]+6)%8]!=magnet[num][right]) turn(num+1, -way);
   }

   idx[num] = (top+8-way)%8;
}

---

3. 결과