[백준] 톱니바퀴 (2) (JAVA)

문제링크:

15662번: 톱니바퀴 (2)

 

 

난이도: 골드 5

 

 

소요시간: 2시간

 

 

문제:

 

톱니바퀴 T개의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.

 

 

입력:

첫째 줄에 톱니바퀴의 개수 T (1 ≤ T ≤ 1,000)가 주어진다. 

 

둘째 줄부터 T개의 줄에 톱니바퀴의 상태가 가장 왼쪽 톱니바퀴부터 순서대로 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.

 

다음 줄에는 회전 횟수 K(1 ≤ K ≤ 1,000)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

 

 

출력:

총 K번 회전시킨 이후에 12시방향이 S극인 톱니바퀴의 개수를 출력한다.

 

문제 이해 :

(본문에 있는 문제가 더 친절함으로 위 내용이 이해가 더 빠를 것이다.)

이 문제는 T개의 톱니바퀴가 주어졌을 때

 

회전 횟수 K가 주어지고, 각 회전마다 어느 톱니를 어느 방향으로 돌릴지가 입력된다.

 

예를 들면 예제 입력 1과 같이 (3, -1) 이 입력되었다면
3번 톱니바퀴를 반시계 방향(-1)으로 회전한다는 뜻이다.

 

이때 중요한 규칙은, 회전 시점마다 서로 마주보고 있는 톱니의 극이 다르면 옆 톱니바퀴가 반대 방향으로 회전한다는 것이다.
반대로, 마주보는 톱니의 극이 같다면 그 옆 톱니는 회전하지 않고 그대로 유지된다.

 

쉽게 예제 입력 1을 예시로 들어보자.

4
10101111
01111101
11001110
00000010
2
3 -1
1 1

먼저 첫 번째 명령 3 -1 에 따라
3번 톱니바퀴가 반시계 방향으로 회전한다.

 

이때 3번과 2번 톱니바퀴가 서로 맞닿아 있는 톱니의 극을 비교했을 때
극이 같으므로 2번 톱니바퀴는 회전에 참여하지 않고 그대로 유지된다.

 

반면 3번과 4번 톱니바퀴가 맞닿은 톱니의 극은 서로 다르기 때문에
4번 톱니바퀴는 3번과 반대 방향, 즉 시계 방향으로 회전하게 된다.

 

두 번째 명령 1 1 에서는
1번 톱니바퀴가 시계 방향으로 회전하고,
이때 1번–2번, 2번–3번, 3번–4번 순서로 마주보는 톱니의 극을 비교하면서
극이 다르면 그다음 톱니는 반대 방향으로,
극이 같으면 더 이상 전달되지 않고 멈추는 식으로 회전이 연쇄적으로 전파된다.

 

이 과정을 모든 회전 명령에 대해 순서대로 적용한 뒤,
최종적으로 각 톱니바퀴의 12시 방향(맨 위 위치)에 있는 톱니의 극을 확인하여
그 위치의 극이 S인 톱니바퀴만 세어서 출력하면 된다.

 

 

구현 방향:

작성자는 먼저 시계 방향 회전 함수와 반시계 방향 회전 함수를 정의하여
각 톱니바퀴를 실제로 회전시키는 기능을 분리해두었다.

 

그 다음, Rotation 함수를 만들어
“어떤 톱니 번호를 어떤 방향으로 회전시킬 것인지” 를 입력받으면
해당 톱니를 기준으로 오른쪽 방향으로 연쇄 회전이 필요한지
그리고 왼쪽 방향으로 연쇄 회전이 필요한지를 각각 탐색하였다.

 

이 탐색 과정에서는
서로 맞닿은 톱니의 극을 비교하여
극이 다르면 반대 방향으로 회전해야 하고,
극이 같으면 그 방향으로 더 이상 탐색이 전파되지 않는 방식으로
회전해야 할 톱니들을 모두 찾아낸다.

 

이렇게 찾은 회전 대상 톱니들과 그 회전 방향들은
리스트에 저장해두고,
앞서 구현해둔 시계/반시계 회전 함수를 이용해
리스트에서 하나씩 꺼내 실제 회전을 수행한다.

 

이 전체 과정을 사용자가 입력한 K번의 회전 명령에 대해 반복 적용함으로써
모든 톱니바퀴의 최종 상태를 계산하게 된다.

 

위와같이 코드를 구현한다면 다음과 같다.

 

 

정답 코드:

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

public class Main {
    static int T,K;
    static int [][]cogs;


    //시게 방향 회전
    public static void rightDirection(int pos){
        int []temp=new int[8];

        //임시 배열 복사
        for(int i=0; i<8; i++){
            temp[i]=cogs[pos][i];
        }

        //시계 방향으로 회전
        for(int i=0; i<8; i++){
            if(i<7){
                cogs[pos][i+1]=temp[i];
            }
            else{
                cogs[pos][0]=temp[7];
            }
        }

    }

    //반시게 방향 회전
    public static void leftDirection(int pos){
        int []temp=new int[8];

        //임시 배열 복사
        for(int i=0; i<8; i++){
            temp[i]=cogs[pos][i];
        }

        //반시계 방향으로 회전
        for(int i=7; i>=0; i--){
            if(i==7){
                cogs[pos][7]=temp[0];
            }
            else{
                cogs[pos][i]=temp[i+1];

            }
        }

    }

    public static void rotation(int pos, int direction){
        List<int[]> list=new ArrayList<>();
        //시계 방향 회전
        if(direction==1){
            boolean flag=true;
            list.add(new int[]{pos,1});
            int temp=pos;

            //시계 방향으로 회전했을때 왼쪽 톱니바퀴들에게 전파
            while (temp>0){
                if(cogs[temp][6]!=cogs[temp-1][2]){
                    if(flag){
                        list.add(new int[]{temp-1,-1});
                        flag=false;
                    }
                    else{
                        list.add(new int[]{temp-1,1});
                        flag=true;
                    }
                    temp--;
                }
                else break;
            }

            temp=pos;
            flag=true;
            //시계 방향으로 회전했을때 오른쪽 톱니바퀴들에게 전파
            while (temp<T-1){
                if(cogs[temp][2]!=cogs[temp+1][6]){
                    if(flag){
                        list.add(new int[]{temp+1,-1});
                        flag=false;
                    }
                    else{
                        list.add(new int[]{temp+1,1});
                        flag=true;
                    }
                    temp++;
                }
                else break;
            }
        }

        else{
            list.add(new int[]{pos,-1});

            int temp=pos;
            boolean flag=true;

            //반시계 방향으로 회전했을때 왼쪽 톱니바퀴들에게 전파
            while (temp>0){
                if(cogs[temp][6]!=cogs[temp-1][2]){
                    if(flag){
                        list.add(new int[]{temp-1,1});
                        flag=false;
                    }
                    else{
                        list.add(new int[]{temp-1,-1});
                        flag=true;
                    }
                    temp--;
                }
                else break;
            }

            temp=pos;
            flag=true;
            //반시계 방향으로 회전했을때 오른쪽 톱니바퀴들에게 전파
            while (temp<T-1){
                if(cogs[temp][2]!=cogs[temp+1][6]){
                    if(flag){
                        list.add(new int[]{temp+1,1});
                        flag=false;
                    }
                    else{
                        list.add(new int[]{temp+1,-1});
                        flag=true;
                    }
                    temp++;
                }
                else break;
            }
        }

        //동시 회전
        for(int[] arr : list ){
            int pos1=arr[0];
            int dir=arr[1];

            if(dir==1){
                rightDirection(pos1);
            }
            else{
                leftDirection(pos1);
            }
        }

    }

    //결과 메서드
    public static int printResult(){
        int result=0;
        for(int i=0; i<T; i++){
            if(cogs[i][0]==1) result++;
        }

        return result;
    }

    public static void main(String[] args) throws IOException {
        //초기 세팅
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        T=Integer.parseInt(br.readLine());

        cogs=new int[T][8];

        for(int i=0; i<T; i++){
            StringBuilder sb=new StringBuilder(br.readLine());
            for(int j=0; j<8; j++){
                cogs[i][j]=sb.charAt(j)-'0';
            }
        }

        K=Integer.parseInt(br.readLine());
        //초기 세팅 끝

        for(int i=0; i<K; i++){
            int n1,n2;
            StringTokenizer st=new StringTokenizer(br.readLine());
            n1=Integer.parseInt(st.nextToken());
            n2=Integer.parseInt(st.nextToken());
            //회전 시작
            rotation(n1-1,n2);

        }

        //최종 결과 출력
        int result = printResult();
        System.out.println(result);


    }

}

 

 

마무리하며:

작성자는 처음에 한 톱니바퀴가 회전한 뒤, 그 변경된 상태를 기준으로 주변 톱니와 비교하여
연쇄 회전을 구현해야 한다고 오해했다.
일반적으로 ‘톱니가 돌면 옆 톱니도 바로 돌아간다’라는 직관 때문에
이렇게 구현하게 된 것으로 보인다.

 

하지만 이 문제의 핵심은 그렇지 않다.
문제에서 원하는 동작은

“기준 톱니가 돌기 전에, 옆 톱니와 극이 다른지 동일한지를 먼저 판단하고
그 판단 결과를 바탕으로 동시에 회전을 적용한다.”

즉, 회전을 적용하기 전에 전체 톱니들의 회전 여부와 방향을 먼저 모두 결정한 뒤,
그 다음에 회전을 실행해야 한다는 것이다.

 

이 부분을 간과하여
작성자는 기준 톱니를 먼저 돌려버리고 그 상태로 주변 톱니를 비교했기 때문에
논리가 어긋났고, 이 문제를 해결하는 데에만 한 시간이 소요되었다.

 

문제 자체는 친절하게 설명되어 있지만,
실제 구현에서는 ‘동시 회전’이라는 조건을 정확히 이해하지 못하면
충분히 혼란이 생길 수 있는 문제이다.

 

따라서 이번 경험을 통해
문제를 정확히 해석하고 시뮬레이션 조건을 꼼꼼히 확인하는 능력의 중요성을 느꼈고,
앞으로는 문제를 무의식적으로 넘기지 않고
요구사항을 더 신중하게 분석해야겠다는 점을 깨닫게 되었다.

 

감사합니다.