백준 14891번: 톱니바퀴
문제 설명
- https://www.acmicpc.net/problem/14891
- 4개의 톱니바퀴가 주어집니다.
- K번 톱니바퀴를 돌립니다.
- 회전하는 톱니바퀴 옆에 있는 톱니바퀴는 서로의 맞닿은 부분의 극값이 반대면 회전합니다.
- 이때 맞닿은 톱니바퀴는 옆의 톱니바퀴와 반대방향으로 회전합니다.
접근법
- List에 톱니바퀴 데이터를 담았습니다. [톱니1,톱니2,톱니3,톱니4]
- 톱니의 회전, 연쇄회전여부는 반복적으로 활용되는 부분이기 때문에 메서드로 구현했습니다.
- addfirst,addlast,pollfirst,polllast의 기능(Deque)과 배열의 값에서 index로 접근하는 기능이(LinkedList) 필요합니다.
- Deque에서 index로의 접근은 불가능하지만 LinkedList에서 first,last기능구현은 가능했기 때문에 LinkedList를 사용했습니다.
- 인접한 톱니바퀴를 확인하는 과정에서 무한루프가 발생할 수 있어 이를 방지하는 Checked 배열을 만들었습니다.
pseudocode
Main(){
for(N번동안){
Turn(처음 주어진 톱니를, 처음 주어진 방향으로);
Checked변수 초기화;
}
점수를 확인합니다.
}
Turn(현재 톱니,방향){
Splash() //현재 톱니의 왼쪽 혹은 오른쪽이 연쇄적으로 돌게 된다면 이들도 재귀적으로 Turn을 실행합니다.
if(방향이 시계방향){
TurnClockWise();
}else{
TurnCounterClockWise();
}
}
TurnClockWise(톱니){
톱니의 맨 뒤에 값을 가장 앞으로 옮깁니다.
}
TurnCounterClockWise(톱니){
톱니의 가장 앞의 값을 맨 뒤로 옮깁니다.
}
Splash(현재톱니, 방향){
if(현재톱니의 왼쪽 톱니를 아직 확인하지 않았다면{
해당 톱니를 체크했다는 표시를 남깁니다.
if(맞닿은 방향이 달라 회전시킬 수 있다면){
Turn(); // 현재톱니와 반대방향으로 왼쪽 톱니를 회전시킵니다.
}
}
if(현재톱니의 오른쪽 톱니를 아직 확인하지 않았다면{
해당 톱니를 체크했다는 표시를 남깁니다.
if(맞닿은 방향이 달라 회전시킬 수 있다면){
Turn(); // 현재톱니와 반대방향으로 오른쪽 톱니를 회전시킵니다.
}
}
}
정답
import java.util.*;
import java.io.*;
public class Main {
static List<Character>[] Gear; // index로 2번과 6번에 접근하기 위해 Deque가 아닌 lst를 썼습니다.
static boolean[] Checked = new boolean[4];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Gear = new LinkedList[4];
StringTokenizer st;
for (int i = 0; i < 4; i++) {
char[] chars = br.readLine().toCharArray();
Gear[i] = new LinkedList<Character>();
for (int j = 0; j < 8; j++) {
Gear[i].add(chars[j]);
}
}
int N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int StartGearNum = Integer.parseInt(st.nextToken());
boolean IsClockWise = (Integer.parseInt(st.nextToken()) == 1) ? true : false;
Turn(StartGearNum - 1, IsClockWise);
Arrays.fill(Checked, false);
}
System.out.println(Score());
}
public static void Turn(int index, boolean direction) {
Checked[index] = true;
Splash(index, direction); // 톱니를 돌리기 전에 맞닿은 톱니의 확인을 먼저 해줘야 합니다.
if (direction) {
TurnClockWise(Gear[index]);
} else {
TurnCounterClockWise(Gear[index]);
}
}
public static void TurnClockWise(List<Character> lst) {
char temp = lst.remove(lst.size() - 1); // pollLast
lst.add(0, temp); // addFirst
}
public static void TurnCounterClockWise(List<Character> lst) {
char temp = lst.remove(0); // pollFirst
lst.add(temp); // addLast
}
public static void Splash(int now, boolean direction) {
// 왼쪽
if (0 <= now - 1 && !Checked[now - 1]) {
Checked[now - 1] = true;
if (Gear[now - 1].get(2) != Gear[now].get(6)) {
Turn(now - 1, !direction);
}
}
// 오른쪽
if (now + 1 < 4 && !Checked[now + 1]) {
Checked[now + 1] = true;
if (Gear[now].get(2) != Gear[now + 1].get(6)) {
Turn(now + 1, !direction);
}
}
}
public static int Score() {
int score = 0;
for (int i = 0; i < Gear.length; i++) {
if (Gear[i].get(0) == '1')
score += Math.pow(2, i);
}
return score;
}
}
기타
아쉬운점
- Turn메서드 내에서 현재 톱니의 회전보다 Splash의 확인이 먼저 일어납니다. 재귀적으로 Turn이 호출되기 때문에 현실에서의 로직과는 다르게 가장 먼 톱니부터 먼저 돌리게 됩니다.
- 예) 3번톱니에 의해 2,4번이 회전하고 2번에 의해 1번이 회전하는 상황이라고 할 때,
제 코드는 현실의 논리인 3 > 2,4 > 1 순서가 아닌 1 > 2,4 > 3로 회전하게 됩니다. - 현재 톱니를 돌린 후 Splash를 실행하려면 맞닿은 부분이 달라지기 때문에 2,6번이 아닌 해당 이빨을 고려하는 작업이 필요합니다.
- 예) 3번톱니에 의해 2,4번이 회전하고 2번에 의해 1번이 회전하는 상황이라고 할 때,
- Deque대신 ArrayList를 사용하는 게 맞을까?
- Deque는 덱의 자료구조적인 특성에 의해 .get(index)메서드가 없는 걸로 알고 있습니다. 그렇다고해서 ArrayList의 add/remove를 0과 마지막 인덱스로 구현한 게 가장 효율적인 방법인지 잘 모르겠습니다.
Author And Source
이 문제에 관하여(백준 14891번: 톱니바퀴), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qwerty1434/백준-14891번-톱니바퀴저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)