[backjoon]14891 톱니 바퀴 java

www.acmicpc.net/problem/14891

14891번: 톱니바퀴

Gold 5

dfs를 이용해서 풀었다.

주의 사항은 현재 상황을 기준으로 톱니바퀴가 움직인다는 것.

즉 만약 1번째를 움직이면 2번째도 움직이는데, 움직인 2번째가 3번째랑 만나서 움직이는 상황이 아니라는 것!

글로 설명이 어려운데, 현재 상황만 생각하지 움직임으로써 발생하는 연쇄 상황은 고려하지 않는다.

따라서, 움직일 상황을 다른 변수에 기록하고 그 변수를 사용하는 방식으로 사용되어야한다.

설명은 복잡한데 막상 문제는 복잡하지 않다.

나는 dfs를 이용해서 풀었는데, 분기처리나 while, for문을 사용해서 풀어도 가능한 듯 싶다.

시계 방향/ 반시계 방향 움직이는 부분이 약간 헷갈렸다.

package com.example.demo;

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

class Main {
	static boolean[] visit;
	static char[][] wheels, wheelsTemp;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		wheels = new char[5][8];
		wheelsTemp = new char[5][8];

		for (int i = 1; i <= 4; i++) {
			wheels[i] = br.readLine().toCharArray();
		}
		
		st = new StringTokenizer(br.readLine());
		int turn = Integer.parseInt(st.nextToken());
		
		for (int i = 1; i <= 5; i++) {
			wheelsTemp = Arrays.copyOf(wheels, i);
		}
		
		while(turn-- > 0) {
			st = new StringTokenizer(br.readLine());
			
			visit = new boolean[5];
			int targetWheel = Integer.parseInt(st.nextToken());
			int dir = Integer.parseInt(st.nextToken());
			
			dfs(targetWheel, dir);
			
			//움직인 부분을 다시 원래의 변수에 넣어준다.
			for (int i = 1; i <= 5; i++) {
				wheels = Arrays.copyOf(wheelsTemp, i);
			}
		}
		
		int sum = 0;
		int point = 1;
		
		for (int i = 1; i <= 4; i++) {
			if( (wheels[i][0]-'0') == 1) sum +=point;
			point *=2;
		}
		
		System.out.println(sum);
	}
	//dfs를 이용하여 접근 할 수 있는 최대치까지 접근한다.
	//이미 변경된 부분은 다시 변경시키지 않기 위해 boolean[]인 visit를 사용.
	//움직임은 한번만 진행되어야한다.
	public static void dfs(int targetWheel, int dir) {
		visit[targetWheel] = true;
		wheelsTemp[targetWheel] = moveTrun(dir, wheels[targetWheel]);
		
		if(targetWheel > 1  && wheels[targetWheel-1][2] != wheels[targetWheel][6]) {
			if(!visit[targetWheel-1])	dfs(targetWheel-1, dir*(-1));
		}
		if(targetWheel < 4 && wheels[targetWheel][2] != wheels[targetWheel+1][6]) {
			if(!visit[targetWheel+1])	dfs(targetWheel+1, dir*(-1));
		}
	}

	//움직임!(1은 시계, 2는 반시계)
	public static char[] moveTrun(int dir, char[] target) {
		char[] result =  new char[8];
		if(dir == -1) {
			for (int i = 1; i < 8; i++) {
				result[i-1] = target[i];
			}
			result[7] = target[0];
		}else if(dir == 1) {
			for (int i = 1; i < 8; i++) {
				result[i] = target[i-1];
			}
			result[0] = target[7];
		}
		return result;
	}
}

문제 자체는 엄청 어렵다 이건 아닌 거 같다...

다만 생각하는 과정이 오래걸렸고, dfs를 진짜 혼자 힘으로 푼 첫 문제인데, 여전히 익숙하지 않은 dfs이기에 시간이 많이 걸린듯 싶다.

생각보다 깔끔하게 풀어서 놀라움 ㅎㅎ