4013 특이한 자석

 

기어를 돌리는 행위를 Queue를 통해 해결하고, 기어의 상태변화를 dfs로 해결했다.

for문으로 사용하는 아이디어가 번거롭다고 생각하여 dfs로 해결했으나, 다른 풀이를 찾아보니, 좌우로 for문을 한번씩 순회하여 해결한 방법이 있었다.

 

for문을 사용하는 경우를 떠올렸을 때, 하나의 for문으로만 해결하려고 했던 것이 문제해결을 복잡하게 만든 원인이었다.

순차 탐색의 경우, 이번 경우를 기억해 두면 쓸모가 있을 것 같다.

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;

class Solution {

	static int N;
	static int[][] gear;
	static int[][] input;
	static int[] check;

	private static int ans;
	private static boolean DBG = false;

	public static void main(String args[]) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T;
		T = Integer.parseInt(br.readLine());

		StringTokenizer st = null;

		for (int test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());

			gear = new int[4][8];

			for (int i = 0; i < 4; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < 8; j++) {
					gear[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			input = new int[N][2];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				input[i][0] = Integer.parseInt(st.nextToken());
				input[i][1] = Integer.parseInt(st.nextToken());
			}
			ans = 0;
			bfs();

			System.out.println("#" + test_case + " " + ans);
		}
	}

	private static void bfs() {
		Queue<int[]> Q = new LinkedList<>();

		for (int[] in : input) {
			Q.offer(in);
		}

		int level = 0;
		while (!Q.isEmpty()) {
			int size = Q.size();
			for (int q = 0; q < size; q++) {
				int[] now = Q.poll();
				int k = now[0] - 1;
				int d = now[1];
				check = new int[4];
				go(0, k, d);
				for (int i = 0; i < check.length; i++) {
					if (DBG)
						System.out.printf("%d ", check[i]);
					shift(gear[i], check[i]);
				}
				if (DBG)
					System.out.println();

				if (DBG) {
					for (int[] ar : gear) {
						for (int v : ar) {
							System.out.printf("%d ", v);
						}
						System.out.println();
					}
				}

			}
			level++;
		}

		int sum = 0;
		int idx = 0;
		for (int[] ar : gear)
			sum += ar[0] * Math.pow(2, idx++);

		ans = sum;
	}

	private static void go(int level, int idx, int d) {

		if (check[idx] != 0)
			return;
		if (DBG)
			System.out.printf("[go] idx : %d d : %d\n", idx, d);
		check[idx] = d;

		if (idx + 1 < 4 && gear[idx][2] != gear[idx + 1][6])
			go(level + 1, idx + 1, d * -1);

		if (idx - 1 >= 0 && gear[idx][6] != gear[idx - 1][2])
			go(level + 1, idx - 1, d * -1);

	}

	static void shift(int[] arr, int d) {
		// 시계
		if (d == 1) {
			int tmp = arr[arr.length - 1];
			int i = 0;
			for (i = arr.length - 1; i > 0; i--) {
				arr[i] = arr[i - 1];
			}
			arr[i] = tmp;
		} else if (d == -1) {// 반시계
			int tmp = arr[0];
			int i = 0;
			for (i = 0; i < arr.length - 1; i++) {
				arr[i] = arr[i + 1];
			}
			arr[i] = tmp;
		} else {
			// d == 0 do nothing.
		}

	}

}

 

 

	private static void checkChaining(int id, int dir) {
		action = new int[4];
		action[id] = dir;
		
		// 현재 자석에서 오른쪽으로
		for(int i = id + 1 ; i < 4 ; ++i) {
			if(magnet[i][6] != magnet[i - 1][2]) {
				action[i] = action[i - 1] == 1 ? -1 : 1;
			} else {
				action[i] = 0;
				break;
			}
		}
		
		// 현재 자석에서 왼쪽으로
		for(int i = id - 1 ; i >= 0 ; --i) {
			if(magnet[i][2] != magnet[i + 1][6]) {
				action[i] = action[i + 1] == 1 ? -1 : 1;
			} else {
				action[i] = 0;
				break;
			}
		}
	}