[ 백준 14891 ] 톱니바퀴 ( 자바 )

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

14891번: 톱니바퀴

 

핵심

1. call by reference가 아닌 call by value로 dfs 값 전달

dfs의 종료 조건들을 상단에 두기 위해서 문제 흐름과 조금 순서가 바뀌었다. 

예를들어 처음 A 톱니바퀴 회전 요청 -> A 톱니바퀴 회전 -> 맞물린 옆 B 톱니바퀴 회전 요청 -> B톱니바퀴가 A톱니바퀴와 맞물린 극이 다른지 체크 -> ... 와 같은 순서로 구현했다. 

그런데 이 때 'B톱니바퀴가 A톱니바퀴와 맞물린 극이 다른지 체크' 수행 시 A 톱니바퀴가 이미 회전해버렸다. 그럼 B 톱니바퀴는 원본이 아닌 회전해버린 A 톱니바퀴와 맞물린 값에서 극을 체크하게 되어 잘못된 답을 찾게 되었다. 

 

>> call by value 형식으로 A 톱니바퀴를 다음 dfs 함수에 전달하여 해결 

 

 

2. dfs 함수 정의 

코드를 어떻게 하면 깔끔하게 할지 생각하다가 dfs 함수 정의를 명확하게 하지 못했다. 그러다보니 생각도 갈피를 못잡고 너무 시간이 오래걸렸다. 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.StringTokenizer;

public class Main {

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

		int[][] gears = new int[4][8];
		for (int i = 0; i < 4; i++) {
			char[] charArray = br.readLine().toCharArray();

			for (int j = 0; j < 8; j++) {
				gears[i][j] = charArray[j] - '0';
			}
		}
		
		int T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			int gearNum = Integer.parseInt(st.nextToken()) - 1;
			int dir = Integer.parseInt(st.nextToken());

			int[] curGear = new int[8];
			for (int i = 0; i < 8; i++) {
				curGear[i] = gears[gearNum][i];
			}
			dfs(gears, gearNum, dir, START, curGear);
		}
		
		System.out.println(gears[0][0] + gears[1][0] * 2 + gears[2][0] * 4 + gears[3][0] * 8);
	}

	/*
	 * gearNum기어를 dir 방향에 따라 회전 영향받는 기어가 옆에 있는면 그 기어도 돌기
	 */
	static final int START = 0;
	static final int LEFT = -1;
	static final int RIGHT = 1;

	/*
	 * 현재 gearnum 검사 
     * gearNum을 dir 방향으로 회전 
     * 첫 시작 기어면 양쪽 영향 
     * from가 왼쪽이면 오른쪽 영향 
     * from가 오른쪽이면 왼쪽 영향
	 * 
	 */
	static void dfs(int[][] gears, int gearNum, int dir, int from, int[] preGear) {
		// 기어 숫자가 아니면 종료
		if (!(gearNum >= 0 && gearNum < 4)) {
			return;
		}

		// 이전 기어와 같은 자석이 맞물려있다면 종료
		if (from == LEFT) {
			if (gears[gearNum][6] == preGear[2]) {
				return;
			}
		} else if(from == RIGHT) {
			if (gears[gearNum][2] == preGear[6]) {
				return;
			}
		}

		// 현재 기어 회전 call by value 
		int[] curGear = new int[8];
		for (int i = 0; i < 8; i++) {
			curGear[i] = gears[gearNum][i];
		}
		rotate(gears, gearNum, dir);

		// 맞물린 기어 회전 요청
		if (from == START) {
			dfs(gears, gearNum - 1, -dir, RIGHT, curGear);
			dfs(gears, gearNum + 1, -dir, LEFT, curGear);

		} else if (from == LEFT){
		/*
		 * 왼쪽기어가 회전했었음 극이 다르면 회전 오른쪽 체크
		 */
			dfs(gears, gearNum + 1, -dir, LEFT, curGear);
			
		} else {
		/*
		 * 오른쪽 기어가 회전했었음 극이 다르면 회전 왼쪽 체크
		 */
			dfs(gears, gearNum - 1, -dir, RIGHT, curGear);
		}
	}

	static void rotate(int[][] gears, int gearNum, int dir) {
		int[] gear = gears[gearNum];
		if (dir == LEFT) {
			int temp = gear[0];
			for (int i = 1; i < 8; i++) {
				gear[i - 1] = gear[i];
			}

			gear[7] = temp;
		} else {
			int temp = gear[7];
			for (int i = 7; i >= 1; i--) {
				gear[i] = gear[i - 1];
			}

			gear[0] = temp;
		}
	}

}