BOJ - 톱니바퀴 14891번 (python, JAVA)

❓ 문제 - 백준 톱니바퀴 14891번 - python, JAVA 풀이법

출처 

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

14891번: 톱니바퀴

 

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

• 톱니 움직일 때마다 왼쪽, 오른쪽 톱니에 대해 다른 극으로 옆에 있는 톱니가 회전할 경우 left(), right() 재귀함수를 활용하여 톱니 상태를 변화시킨다.
• 톱니를 회전할 때 queue를 활용하여 시계방향으로 톱니가 회전할 경우 rotate(1), 반시계방향으로 톱니가 회전할 경우 (-1)으로 구현한다.
• left() : 현재톱니에서 왼쪽 톱니가 존재할 때 현재 톱니의 6번째 인덱스랑 왼쪽 톱니의 3번째 인덱스가 만나므로 서로 양극인지 확인하여 서로 다른 극이라면 왼쪽 톱니를 반대방향으로 돌게하고 재귀함수를 통해 왼쪽 톱니의 왼쪽을 확인한다.
• right() : 현재톱니에서 오른쪽 톱니가 존재할 때 현재 톱니의 3번째 인덱스랑 오른쪽 톱니의 6번째 인덱스가 만나므로 서로 양극인지 확인하여 서로 다른 극이라면 오른쪽 톱니를 반대방향으로 돌게하고 재귀함수를 통해 오른쪽 톱니의 오른쪽을 확인한다.

 

 

💻 소스코드 (python)

from collections import deque
chain = [deque(list(input())) for _ in range(4)]
k = int(input())

def left(now, l, dir):
    if l < 0:
        return
    if chain[now][6] != chain[l][2]:
        left(l, l-1, -dir)
        chain[l].rotate(-dir)

def right(now, r, dir):
    if r > 3:
        return
    if chain[now][2] != chain[r][6]:
        right(r, r+1, -dir)
        chain[r].rotate(-dir)

for _ in range(k):
    num, dir = map(int, input().split())
    left(num-1, num-2, dir)
    right(num-1, num, dir)
    chain[num-1].rotate(dir)

answer = 0
for i in range(4):
    if chain[i][0] == "1":
        answer += (2**i)

print(answer)

 

 

💻 소스코드 (JAVA)

// BOJ - 톱니바퀴(14891번)
// DFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main_14891 {
	public static ArrayList<ArrayList<Integer>> chain;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		chain = new ArrayList<>();
		for(int i=0;i<4;i++) {
			String[] input = br.readLine().split("");
			ArrayList<Integer> list = new ArrayList<Integer>();
			for(int j=0;j<8;j++) {
				list.add(Integer.parseInt(input[j]));
			}
			chain.add(list);
		}

		int k = Integer.parseInt(br.readLine());
		for(int i=0;i<k;i++) {
			String[] input = br.readLine().split(" ");
			int num = Integer.parseInt(input[0]) -1;
			int rotate = Integer.parseInt(input[1]);

			// 왼쪽 회전
			rotate_left(num, rotate);
			rotate_right(num, rotate);
			if(rotate == 1) {
				int last = chain.get(num).get(7);
				chain.get(num).remove(7);
				chain.get(num).add(0, last);

			} else {
				int first = chain.get(num).get(0);
				chain.get(num).remove(0);
				chain.get(num).add(7, first);
			}

		}
		int sum = 0;
		for(int i=0;i<4;i++) {
			if(chain.get(i).get(0) == 1) sum += Math.pow(2, i);
		}

		System.out.println(sum);

	}

	public static void rotate_left(int num, int rotate) {
		if(num == 0) return;

		if(chain.get(num).get(6) != chain.get(num-1).get(2)) {
			rotate = -rotate;
			rotate_left(num-1, rotate);

			if(rotate == 1) {
				int last = chain.get(num-1).get(7);
				chain.get(num-1).remove(7);
				chain.get(num-1).add(0, last);

			} else {
				int first = chain.get(num-1).get(0);
				chain.get(num-1).remove(0);
				chain.get(num-1).add(7, first);
			}

		}
	}

	public static void rotate_right(int num, int rotate) {
		if(num == 3) return;

		if(chain.get(num).get(2) != chain.get(num+1).get(6)) {
			rotate = -rotate;
			rotate_right(num+1, rotate);

			if(rotate == 1) {
				int last = chain.get(num+1).get(7);
				chain.get(num+1).remove(7);
				chain.get(num+1).add(0, last);

			} else {
				int first = chain.get(num+1).get(0);
				chain.get(num+1).remove(0);
				chain.get(num+1).add(7, first);
			}

		}
	}

}