엔지니어링 선표는 일을 하던 도중 창고에서 특이한 자석이 놓여있는 판을 발견했다. 이 판에는 4개의 자석이 놓여져 있었고, 각 자석은 8개의 ‘날’(튀어나온 곳)를 가지고 있다. 자석의 각 날 마다 N 극 또는 S 극의 자성을 가지고 있다. 이 특이한 자석은 [Fig. 1] 과 같이 1 번부터 4 번까지 판에 일렬로 배치되어 있고, 빨간색 화살표 위치에 날 하나가 오도록 배치되어 있다.
심심한 선표는 이 특이한 자석을 가지고 놀아보니 신기한 규칙을 발견했다. 임의의 자석을 1 칸씩 K 번 회전시키려고 해보니, 하나의 자석이 1 칸 회전될 때, 붙어 있는 자석은 서로 붙어 있는 날의 자성과 다를 경우에만 인력에 의해 반대 방향으로 1 칸 회전된다. 이를 신기하게 생각한 선표는 무작위로 자석을 돌렸을 때, 모든 회전이 끝난 후, 아래와 같은 방법으로 점수를 계산을 하고자 한다. - 1 번 자석에서 빨간색 화살표 위치에 있는 날의 자성이 N 극이면 0 점, S 극이면 1 점을 획득한다. - 2 번 자석에서 빨간색 화살표 위치에 있는 날의 자성이 N 극이면 0 점, S 극이면 2 점을 획득한다. - 3 번 자석에서 빨간색 화살표 위치에 있는 날의 자성이 N 극이면 0 점, S 극이면 4 점을 획득한다. - 4 번 자석에서 빨간색 화살표 위치에 있는 날의 자성이 N 극이면 0 점, S 극이면 8 점을 획득한다.
4 개 자석의 자성 정보와 자석을 1 칸씩 K 번 회전시키려고 할 때, K 번 자석을 회전시킨 후 획득하는 점수의 총 합을 출력하는 프로그램을 작성하라.
설명
구현 문제이다. 특이한 자석과 같이 일반적인 구현 문제의 경우 특별한 알고리즘을 요구하지 않으며 기본적인 자료구조만 잘 다루고 데이터들을 정확하게 처리한다면 풀 수 있다. 단 문제의 길이가 길어질수록 디버깅 과정이 복잡해지기 때문에 문제에서 요구하는 각 기능들을 객체화 시키는게 중요하다.
자석은 돌아가며 돌아가는 방향에 따라 배열의 순서가 바뀐다. 시계방향 또는 반시계방향으로 돌기때문에 자료구조 덱을 사용하여 N극과 S극을 저장했다.
어떤 자석을 돌릴 때 왼쪽 자석과 오른쪽 자석이 존재한다면 같이 돌아갈 수도 있다. 왼쪽 자석의 3번째 날의 자성과 현재 자석의 7번째 날 그리고 현재 자성의 3번째 날의 자성과 오른쪽 자석의 7번째 날의 자성이 다르다면 왼쪽 자석과 오른쪽 자석이 함께 돌아간다. 어떤 자석에 대해 돌아가는 과정은 동일하고 해당 자석이 왼쪽 혹은 오른쪽 자석을 돌릴 수 있냐 없냐의 문제이기 때문에 재귀함수를 통해 구현했다.
만약 현재 자석(N)에 대해서 왼쪽 자석(N-1)이 존재하고 왼쪽 자석(N-1)을 돌릴 수 있다면 일단 현재 자석(N)만 돌리고 왼쪽 자석(N-1)에 대해서 재귀함수를 돌린다. 단 이때 왼쪽 자석(N-1)의 재귀함수에서는 왼쪽 자석이 돌아갈 때 원래 있던 자석(N)이 돌아갈 수 있더라도 돌아가서는 안 된다. 이를 위해 해당 자석이 어느 방향으로 나아가야 하는지 여부도 매개변수에 추가해줬다.
오른쪽도 마찬가지다.
코드
//4013. 특이한 자석.java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.StringTokenizer;
public class 특이한_자석_4013 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws NumberFormatException, IOException {
int T = Integer.parseInt(br.readLine());
for(int t=1;t<=T;t++) {
int K = Integer.parseInt(br.readLine());
//(0,2)-(1,6)
List<Deque<Integer>> magnet = new ArrayList<>();
for(int i=0;i<4;i++) {
magnet.add(new ArrayDeque<>());
st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<8;j++) {
magnet.get(i).addLast(Integer.parseInt(st.nextToken()));
}
}
int[][] spin = new int[K][2];
for(int k=0;k<K;k++) {
st = new StringTokenizer(br.readLine()," ");
spin[k][0] = Integer.parseInt(st.nextToken())-1;
spin[k][1] = Integer.parseInt(st.nextToken());
spinMagnut(spin[k], magnet, true, true);
}
int answer=0;
for(int i=0;i<4;i++) {
if(magnet.get(i).pollFirst()==1) {
answer += Math.pow(2, i);
}
}
sb.append("#"+t+" "+answer+"\n");
}
System.out.println(sb.toString());
}
static void spinMagnut(int[] magnetData,List<Deque<Integer>> magnet, boolean left, boolean right) {
//현재 자석이 다른 자석을 돌리는지 확인
int leftMagnet = magnetData[0]-1;
boolean leftCheck = false;
if(leftMagnet>=0) {
if(magnet.get(leftMagnet).toString().charAt(7)+magnet.get(magnetData[0]).toString().charAt(19) == 97) {
//왼쪽 자석 돌리기
leftCheck=true;
}
}
int rightMagnet = magnetData[0]+1;
boolean rightCheck = false;
if(rightMagnet<4) {
if(magnet.get(rightMagnet).toString().charAt(19)+magnet.get(magnetData[0]).toString().charAt(7) == 97) {
//오른쪽 자석 돌리기
rightCheck=true;
}
}
//현재 자석 돌리기
if(magnetData[1]==1) {//시계방향
int temp = magnet.get(magnetData[0]).pollLast();
magnet.get(magnetData[0]).addFirst(temp);
}
else {
int temp = magnet.get(magnetData[0]).pollFirst();
magnet.get(magnetData[0]).addLast(temp);
}
//왼쪽 돌리기
if(leftCheck && left) {
spinMagnut(new int[]{leftMagnet, magnetData[1]*(-1)}, magnet,true,false);
}
//오른쪽 돌리기
if(rightCheck && right) {
spinMagnut(new int[]{rightMagnet, magnetData[1]*(-1)}, magnet,false,true);
}
}
}
