[백준/자바] 14891번: 톱니바퀴

문제

https://www.acmicpc.net/problem/14891

풀이

• 8개의 톱니를 가지고 있는 톱니바퀴 4개가 일렬로 배치
• 톱니는 N극 또는 S극을 나타냄
• 톱니바퀴를 총K번 회전시키려고 함
  • 회전은 시계 방향과 반시계 방향으로 한 칸씩 가능
• 임의의 톱니바퀴 A를 회전시킬 때 맞닿은 톱니의 극이 다르다면 B는 반대 방향으로 회전

회전하려는 톱니바퀴를 기준으로 왼쪽, 오른쪽을 분할하여 탐색했습니다.
다른 극이라면 반대 방향으로 설정, 같은 극이라면 탐색을 종료하는 방식을 선택

	private static void simulate(int idx, int d) {
		int[] dir = new int[4];
		dir[idx] = d;
		
        // 왼쪽 탐색
		for (int i = idx - 1; i >= 0; i--) {
			if (cog[i+1][LEFT] == cog[i][RIGHT]) break;
			dir[i] = -dir[i+1];
		}
		
        // 오른쪽 탐색
		for (int i = idx + 1; i < 4; i++) {
			if (cog[i-1][RIGHT] == cog[i][LEFT]) break;
			dir[i] = -dir[i-1];
		}
		
		rotate(dir);
	}

여기서 LEFT, RIGHT는 각각 인접한 톱니바퀴와 맞닿는 왼쪽, 오른쪽 인덱스인 2와 6으로 선언되어 있습니다.

탐색이 종료되면 회전을 시킵니다.

	private static void rotate(int[] dir) {
		for (int i = 0; i < 4; i++) {
			if (dir[i] == 0) continue;
			
			Deque<Integer> queue = new ArrayDeque<>();
			
			for (int idx = 0; idx < 8; idx++) queue.add(cog[i][idx]);
			
			if (dir[i] == 1) queue.offerFirst(queue.pollLast());
			else if (dir[i] == -1) queue.offerLast(queue.pollFirst());
			
			for (int idx = 0; idx < 8; idx++) cog[i][idx] = queue.pollFirst();
		}
	}

큐에 값을 넣고 시계방향일 경우 마지막에 있는 값을 앞에 추가, 반시계 방향일 경우에는 앞에 있는 값을 마지막 인덱스에 추가하였습니다.

	private static void scoring() {
		for (int i = 0; i < 4; i++) {
			if (cog[i][0] == 1) {
				answer += (1 << i);
			}
		}
	}

모든 탐색을 마치면 2의 i제곱으로 값을 계산하였습니다.

소소한 팁

입력 인덱스가 1부터 시작하므로, 0-base list를 사용하신다면 입력 받을 때 -1을 해주셔야 합니다 ‼️

코드

import java.util.*;
import java.io.*;

public class Main_14891 {
	static int[][] cog = new int[4][8];
	static final int LEFT = 6;
	static final int RIGHT = 2;
	static int answer = 0;
	
	private static void simulate(int idx, int d) {
		int[] dir = new int[4];
		dir[idx] = d;
		
		for (int i = idx - 1; i >= 0; i--) {
			if (cog[i+1][LEFT] == cog[i][RIGHT]) break;
			dir[i] = -dir[i+1];
		}
		
		for (int i = idx + 1; i < 4; i++) {
			if (cog[i-1][RIGHT] == cog[i][LEFT]) break;
			dir[i] = -dir[i-1];
		}
		
		rotate(dir);
	}
	
	private static void rotate(int[] dir) {
		for (int i = 0; i < 4; i++) {
			if (dir[i] == 0) continue;
			
			Deque<Integer> queue = new ArrayDeque<>();
			
			for (int idx = 0; idx < 8; idx++) queue.add(cog[i][idx]);
			
			if (dir[i] == 1) queue.offerFirst(queue.pollLast());
			else if (dir[i] == -1) queue.offerLast(queue.pollFirst());
			
			for (int idx = 0; idx < 8; idx++) cog[i][idx] = queue.pollFirst();
		}
	}
	
	private static void scoring() {
		for (int i = 0; i < 4; i++) {
			if (cog[i][0] == 1) {
				answer += (1 << i);
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for (int i = 0; i < 4; i++) {
			String line = br.readLine();
			for (int j = 0; j < 8; j++) {
				cog[i][j] = line.charAt(j) - '0';
			}
		}
		
		int k = Integer.parseInt(br.readLine());
		for (int i = 0; i < k; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int idx = Integer.parseInt(st.nextToken());
			int dir = Integer.parseInt(st.nextToken());
			simulate(idx - 1, dir);
		}
		
		scoring();
		System.out.println(answer);
	}

}

여담

어느새 싸피에 입과한 지 어언 2달..
과제에 치여 살다 보니, 게시물 업데이트가 굉장히 뜸했었습니다..
이번 달부터는 다시 하루에 하나는 꼭 업데이트하도록 노력하려고 합니다 😂
항상 초심 잃지 않고 열심히 삽시다!!