백준 14891 톱니바퀴 (java) 반례포함

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

구현문제

특정 톱니를 선택해서 시계방향이나 반시계방향으로 한칸 돌린다.

톱니가 돌아갈때 인접 톱니도 돌지만 맞물리는 부분이 같은 극성이면 돌지않는다.

위에서 1번톱니를 돌릴때 2번톱니는 돌지만

2번톱니가 돌면서 3번톱니가 돌지는 않는다.(2번과 3번 맞물리는게 둘다 S로 같은 극성이다)

 

헷갈릴 수 있는 부분이 있는데 틀렸던 코드를 첨부한다,

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


public class Main {
    static int[][] wheels = new int[4][10]; // 4개에 10칸 할거야. 필요칸은 8칸인데, 0은 반시계시 끝에, 9는 시계시 처음으로 붙이기
    static int n;

    public static void spinmanage(int wheel, int direc, int c) {
        /*
        연쇄적으로 회전을 해야하네? 그치만 연쇄적일때는 한쪽방향으로만 가야해
        케이스를 같이 받아서, 1은 양쪽다보고 나도돌린다, 0은 왼쪽만체크, 2는 오른쪽만체크
         */
        if (c != 2) {
            if (wheel >= 1) {
                if (wheels[wheel][7] != wheels[wheel - 1][3]) {
                    spinmanage(wheel-1,direc*-1,0);
                    spin(wheel - 1, direc * -1);

                }
            }
        }
        if (c != 0) {
            if (wheel <= 2) {
                if (wheels[wheel][3] != wheels[wheel + 1][7]) {
                    spinmanage(wheel+1,direc*-1,2);
                    spin(wheel + 1, direc * -1);

                }
            }
        }
        if (c == 1) {
            spin(wheel, direc);
        }
    }

    public static void spin(int wheel, int direc) {
        if (direc == 1) {
            for (int i = 9; i >= 2; i--) {
                wheels[wheel][i] = wheels[wheel][i - 1];
            }
            wheels[wheel][1] = wheels[wheel][9];
        } else if (direc == -1) {
            for (int i = 0; i <= 7; i++) {
                wheels[wheel][i] = wheels[wheel][i + 1];
            }
            wheels[wheel][8] = wheels[wheel][0];
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str = "";
        for (int i = 0; i < 4; i++) {
            str = br.readLine();
            for (int j = 0; j < 8; j++) {
                wheels[i][j + 1] = str.charAt(j) - '0';
            }
        }
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            str = br.readLine();
            StringTokenizer token = new StringTokenizer(str);
//            wheelnum[i]=Integer.parseInt(token.nextToken());
//            direction[i]=Integer.parseInt(token.nextToken());
            int wheel = Integer.parseInt(token.nextToken()) - 1;
            int direc = Integer.parseInt(token.nextToken());
            spinmanage(wheel, direc, 1);
        }
        int result = 0;
        for (int i = 0; i < 4; i++) {
            if (wheels[i][1] == 1) {
                result += (1 << i);
                //System.out.println(result);
            }
        }
        System.out.println(result);
//        for(int i=0;i<4;i++){
//            for(int j=1;j<=8;j++){
//                System.out.print(wheels[i][j]);
//            }
//            System.out.println();
//
//        }
    }
}

 

이부분이 문제였다. 톱니는 하나 돌면 맞물린 톱니들이 동시에 연쇄적으로 같이 반응한다.

하지만 위와 같이 재귀를 구현하면 옆 톱니를 우선 한칸 돌리고 옆 톱니의 상황을 고려하게 된다.

이 그림의 예시에서, 3번이 시계방향으로 돌면 4번과 3번이 맞물린 곳의 극성이 다르기 때문에 돌아야 하지만,

2번과 3번 맞물린 자리가 같지 않다는 가정 하에, 2번이 돌면서 3번이 시계방향으로 연쇄적으로 돌 때

3번의 4번방향 톱니가 S로 바뀌게되면서 4번 톱니바퀴가 돌지 않게된다.

처음 상태에서 연쇄작용을 고려하기 위해 spin함수의 호출 전에 spinmange 함수가 호출되어야 한다.

 

위 상황을 잘못 구현하셨을 때의 반례

 

11011111
11011111
00000111
00000000
1
1 1

입력시

7이 나와야 함