백준 - 톱니바퀴

문제 설명

톱니바퀴 4개가 주어진다.

톱니바퀴 하나를 회전화면 주의에 톱니바퀴가 돌아가게 된다.

주의의 톱니바퀴가 돌아가는 조건은 서로 맞물려있는 부분이 서로 다른 성질을 가지면 된다.

주어진 명령에 의해 해당 톱니바퀴를 돌리고 주어진 점수를 할당하여 점수를 구하는 문제이다.

• 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
• 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
• 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
• 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

풀이

맞물려있는 부분은 배열의 2번째 칸 6번째 칸이다.

하지만 맨 끝에 위치한 톱니바퀴는 왼쪽 또는 오른쪽에 아무것도 없다.

해당 문제에서 중요한 것은 전파이다.

전파력이 어디까지 도달할 수 있는지 먼저 파악하고 끝에서부터 톱니바퀴를 돌려야 한다. (채택 방법)

미리 돌리면 이전 정보가 이미 갱신되었기 때문에 문제가 될 수 있다. 하지만 이전 정보를 기억하면 상관이 없다.

public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		int gears[][] = new int[4][8];
		for (int i = 0; i < 4; i++) {
			String[] str = reader.readLine().split("");
			for (int j = 0; j < 8; j++) {
				gears[i][j] = Integer.parseInt(str[j]);
			}
		}

		int n = Integer.parseInt(reader.readLine());
		int[][] cmd = new int[n][2];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			cmd[i][0] = Integer.parseInt(st.nextToken());
			cmd[i][1] = Integer.parseInt(st.nextToken());
		}

		System.out.println(solution(gears, cmd));
	}

	static int g[][];

	static int solution(int[][] gears, int[][] cmds) {
		int answer = 0;
		g = gears;
		for (int[] cmd : cmds) {
			int idx = cmd[0] - 1;
			int dir = cmd[1];
			if (dir == 1) { // 시계
				// 왼쪽, 오른쪽 전파까지 계속 해야함.
				v[idx] = true;
				go(idx, dir);
				v[idx] = false;
			} else {
				v[idx] = true;
				go(idx, dir);
				v[idx] = false;
			}
		}

		int score = 1;
		for (int i = 0; i < 4; i++) {
			answer += gears[i][0] == 1 ? score : 0;
			score *= 2;
		}

		return answer;
	}

	static boolean v[] = new boolean[4];
  // 전파 시작
	static void go(int idx, int dir) {
		if (idx <= 2 && !v[idx + 1] && g[idx][2] != g[idx + 1][6]) {
			v[idx + 1] = true;
			go(idx + 1, dir * -1);
			v[idx + 1] = false;
		}

		if (idx >= 1 && !v[idx - 1] && g[idx][6] != g[idx - 1][2]) {
			v[idx - 1] = true;
			go(idx - 1, dir * -1);
			v[idx - 1] = false;
		}

    // 전파가 모두 완료된후 끝에서부터 하나씩 돌려간다.
		if (idx == 0 || idx == 3) {
			rotate(dir, idx);
		} else {
			rotate(dir, idx);
		}
	}

	static void rotate(int dir, int idx) {
		if (dir == 1) {
			int temp = g[idx][7];

			for (int i = 7; i > 0; i--) {
				g[idx][i] = g[idx][i - 1];
			}

			g[idx][0] = temp;
			return;
		}

		int temp = g[idx][0];

		for (int i = 0; i < 7; i++) {
			g[idx][i] = g[idx][i + 1];
		}

		g[idx][7] = temp;
	}