[문제 풀이] 백준 14891번 톱니바퀴 JAVA

문제

 

 

 

  문제접근 방법   

해당 문제는 8개의 톱니를 가지고 있는 4개의 톱니바퀴 각 톱니가 N과 S극으로 이루어져 있다. 

이때 톱니의 N/S극 구성, 움직려는 톱니의 수와 톱니 번호, 이동방향을 알려준다면 최종적으로 12시 방향의 톱니가 

N인지 S인지 파악하고 점수를 계산해 최종 점수를 추력하는 문제이다.

처음에는 문제를 보고 원형큐로 구현하려고 하였지만 시간복잡도가 올라가 실패할 확률도 존재하는 것으로 판단해

원형큐이긴 하지만 좌표만 이동하는 방식으로 문제를 접근하였다.

접근 방법은 쉽게 떠올랐지만 문제안의 구성이 생각보다 어려웠다. 고려해 줄 부분이 상당히 많았다고 느끼었다.

실제로도 많이 시도하였고  1시간 전이라고 나와있지만 2시간은 넘게 문제를 잡고 있었다.

 

여기서 고려해줄 부분들을  간단하게 설명하고 아래 코드에서 더 필요한 설명이 있다면 추가해서 설명하겠다.

먼저 돌리고 싶은 톱니 번호와 이동 방향을 입력받는데 해당 톱니는 무조건 입력 방향으로 돌아간다.

이는 n극 s극 과는 상관이 없다. n극과 s극을 가지고 있는 톱니가 서로 같은 극이면 움직이지 않고 서로 다른 극이라면 움직인다.

라는 부분 때문에 무조건 돌아간다는 조건을 도출하기까지 많은 시간을 소요했다. 

문제를 풀이할때 같은 극이면 멈추고 다른 극이면 서로 반대방향으로 돌아간다에 집중해 문제를 접근했던 것이 문제였다.

이 조건을 발견한 것은 테스트 코드를 돌리는 과정에서 톱니가 서로 맞물리는 부분이 모두 같은 극이면 움직이지 않는 것인가?라는

의문이 생겨 발견한 부분이다. 마지막 조건은 톱니는 차례로 돌아가는 것이 아닌 한 번에 돌아간다는 것이다.

처음에는 톱니를 차례로 돌려 진행하려 했지만 이럴 경우 값이 이상해져 원하는 출력을 구할 수가 없었다.

이 4가지 조건을 생각하면서 문제에 접근한다면 어렵긴 하지만 풀 수 있을 것이라고 생각된다.

 

< 초기 코드  >

import java.util.*;

public class Main{
    public static int move[]={2,2,2,2};
    public static int temp[];
    public static boolean visited[];
    public static StringBuilder sb=new StringBuilder();
    public static void  main(String args[]){
        Scanner s=new Scanner(System.in);
        int cogwheel[][]=new int[4][8];
        for(int i=0;i<cogwheel.length;i++){
            String str=s.next();
            for(int j=0;j<cogwheel[0].length;j++){
                // N 0 ,S 1
                cogwheel[i][j]=str.charAt(j)-'0';
            }
        }
        
        int test=s.nextInt();
        for(int t=0;t<test;t++){
            int number=s.nextInt();
            int direction=s.nextInt();// 시계방향 1, 반시계방향 -1 
            temp=new int[4];
            cogwheelStatus(cogwheel,number,direction);
        }
        System.out.print(sb);       
    }
    
    //회전시 같은 극이면 멈춰있고 다른 극이면 회전한다.(하나는 시계, 하나는 반시계방향으로 회전함)
    public static void cogwheelStatus(int cogwheel[][],int number,int direction){
        
        temp[number-1]=direction;
        
        for(int i=number;i<4;i++){
            if(cogwheel[i-1][move[i-1]]==cogwheel[i][(move[i]+4)%8])break;
            temp[i]=-1*temp[i-1];
            
        }
        for(int i=number-1;i>0;i--){
            if(cogwheel[i-1][move[i-1]]==cogwheel[i][(move[i]+4)%8])break;
            temp[i]=-1*temp[i-1];
            
        }
        for(int i=0;i<4;i++){
            if(temp[i]==1){
                move[i]=(move[i]+1)%8;
            }
            else if(temp[i]==-1){
                move[i]=(move[i]+7)%8;
            }
        }
        
        int sum=0;
        for(int i=0;i<4;i++){
            if(cogwheel[i][(move[i]+6)%8]==1){
                switch(i){
                    case 0:
                        sum+=1;
                        break;
                    case 1:
                        sum+=2;
                        break;
                    case 2:
                        sum+=4;
                        break;
                        
                    case 3:
                        sum+=8;
                        break;
                }
            }
        }
        sb.append(sum).append("\n");
    }
}

 

여러 시도들을 했고 많은 시도가 있었지만 문제에 비슷하게 접근했지만 틀린 부분이 있어 그 부분이 담긴 초기 코드를 가져왔다.

먼저 간단한 코드의 흐름은 회전하는 방향과 회전 톱니 번호를 입력받으면 해당 톱니가 어디로 돌아가는지 저장해 준다.

이게 무슨 말이냐면 톱니는 하나씩 돌아가는 것이 아니라 하나가 움직이면 모두가 같이 움직이는 것이다. 그런데 어떤 톱니를 먼저 돌려버리고 이 값을 기준으로 다른 톱니와 비교하면 원하는 방향이 아닌 다른 방향의 코드가 작성된다. 그리고 입력된 톱니를 기준으로 움직이기 때문에 처음 입력된 톱니의 값을 먼저 저장하고 해당 값을 기준으로 다른 톱니들의 이동 방향을 정해주었다. 또 같은 극이라면 그 이후의 톱니들은 어차피 움직이지 못하니 break 해주었다. 이후 최종에서 톱니의 좌표를 저장하는 move에 temp값을 기준으로 이동해 주었고 sum에 값을 저장해 출력해 주었다.

 

이렇게 작성했지만 해당 코드는 통과하지 못했고 자꾸 틀린 출력들이 나오기에 코드를 살펴보았다.

 

문제는 2 부분이었는데 sum부분과 move값에 temp값을 반영해 주는 부분에서 문제가 발생하였다. sum은 모든 톱니 이동이 끝나고 출력 직전에 해주어야 하는데 본인의 코드는 처음 톱니 이동하고 더하고 다음 톱니 이동하면 별도로 더하고 해서 각각의 합이 나온다. 하지만 문제에서 원하는 것은 입력받은 톱니 이동을 마치고 점수를 계산해 출력하는 것이라 이 부분을 수정하였다.

2 번제는 move에 temp를 반영해 주는 부분에서 시계 방향과 반시계방향을 혼동하여 반대로 작성해 버린 것이 문제가 되어 수정하였다. 수정한 최종 코드는 아래와 같다.

< 최종 코드 >

import java.util.*;

public class Main{
    public static int move[]={2,2,2,2};
    public static int temp[];
    public static void  main(String args[]){
        Scanner s=new Scanner(System.in);
        int cogwheel[][]=new int[4][8];
        for(int i=0;i<cogwheel.length;i++){
            String str=s.next();
            for(int j=0;j<cogwheel[0].length;j++){
                // N 0 ,S 1
                cogwheel[i][j]=str.charAt(j)-'0';
            }
        }
        
        int test=s.nextInt();
        for(int t=0;t<test;t++){
            int number=s.nextInt();
            int direction=s.nextInt();// 시계방향 1, 반시계방향 -1 
            temp=new int[4];
            cogwheelStatus(cogwheel,number-1,direction);
        }
        int sum=0;
        for(int i=0;i<4;i++){
            if(cogwheel[i][(move[i]+6)%8]==1){
                switch(i){
                    case 0:
                        sum+=1;
                        break;
                    case 1:
                        sum+=2;
                        break;
                    case 2:
                        sum+=4;
                        break;
                        
                    case 3:
                        sum+=8;
                        break;
                }

            }
        }
        System.out.print(sum);       
    }
    
    //회전시 같은 극이면 멈춰있고 다른 극이면 회전한다.(하나는 시계, 하나는 반시계방향으로 회전함)
    public static void cogwheelStatus(int cogwheel[][],int number,int direction){
        
        temp[number]=direction;
        
        for(int i=number;i<3;i++){
            if(cogwheel[i][move[i]]==cogwheel[i+1][(move[i+1]+4)%8])break;
            temp[i+1]=-1*temp[i];
            
        }
        for(int i=number;i>0;i--){
            if(cogwheel[i-1][move[i-1]]==cogwheel[i][(move[i]+4)%8])break;
            temp[i-1]=-1*temp[i];
            
        }
        for(int i=0;i<4;i++){
            if(temp[i]==1){
                move[i]=(move[i]+7)%8;
                
            }
            else if(temp[i]==-1){
                move[i]=(move[i]+1)%8;
            }
        }
        
        

    }
}

위에서 언급한 부분 중 sum은 함수가 아닌 main 함수의 출력 전으로 이동시키고  move 계산하는 부분의 시계방향과 반시계 방향을 올바르게 수정해 주었다. 이후 코드는 원하는 데로 잘 돌아가는 것을 확인하였다.

 

  마무리  

해당 문제는 구현과 시뮬레이션 문제로 톱니바퀴의 이동 방향을 계산하고 최종에는 점수로 계산하는 문제였다. 

어떤 식으로 코드를 작성할지는 빠르게 떠올랐지만 문제 내부 코드 작성과 조건 구현들에 시간이 많이 걸렸다. 

별다른 알고리즘 없이 풀이가 가능하지만 역설적이게도 어렵웠다. 그래서 더 많이 풀어보고 보완해야겠다는 생각이 들었다.