[JAVA] 15662 - 톱니바퀴 (2) 💛5: 역할을 확실하게 나누자..! - 시뮬레이션 정복기

들어가며

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

문제가 굉장히 길다. 시뮬레이션 문제다. 시뮬레이션 문제는 정말 정신 똑바로 차리지 않고 문제풀이에 들어가면 미궁속으로 빠진다.

 

톱니바퀴들의 맞물려있는 톱니끼리의 극을 확인하고, 서로 다른 극이라면 전 톱니바퀴 회전방향의 반대방향으로 회전한다. 모든 Operation이 끝났을때 윗부분의 톱니의 극이 S인 톱니가 몇개인지 정답으로 출력하면 되는 문제이다.

본문으로

딱 문제 처음 읽었을때 다음 4가지의 방법으로 생각했다

1. 기존 톱니바퀴를 돌려본다.

2. 왼쪽 톱니바퀴 돌려야하나?

3. 오른쪽 톱니바퀴 돌려야하나?

4. 확인하고 실제로 돌린다...

나름 4가지로 분기를 나누고 자신있게 로직 작성에 들어갔다. 아래의 로직을 작성했다.(틀린 풀이이니 자세히 보지는 말자..ㅎㅎㅎ)

public class Main {

    static int T, K, ret;
    static int[][] topnis;
    static List<Oper> opers;

    static class Oper {
        int topni;
        int dir;

        Oper(int topni, int dir) {
            this.topni = topni;
            this.dir = dir;
        }
    }

    static void rotate(int topni, int dir) {
        int[][] dTopnis = new int[T][8];
        boolean isDouble = false;
        if (topni == 0) { // 첫번째면 오른쪽으로만
            dTopnis = goRight(topni, dir);
            syncRight(dTopnis, topni);
        } else if (topni == T - 1) { // 마지막꺼면 왼쪽으로만
            dTopnis = goLeft(topni, dir, isDouble);
            syncLeft(dTopnis, topni);
        } else { // 양옆으로 확인
            isDouble = true;
            dTopnis = goLeft(topni, dir, isDouble);
            int[][] rTopnis = new int[T][8];
            rTopnis = goRight(topni, dir);
            syncLeft(dTopnis, topni);
            syncRight(rTopnis, topni);
        }
    }

    static void syncRight(int[][] dTopnis, int topni) {
        for (int i = topni; i < T; i++) {
            for (int j = 0; j < 8; j++) {
                topnis[i][j] = dTopnis[i][j];
            }
        }
    }

    static void syncLeft(int[][] dTopnis, int topni) {
        for (int i = topni; i >= 0; i--) {
            for (int j = 0; j < 8; j++) {
                topnis[i][j] = dTopnis[i][j];
            }
        }
    }

    static int[][] goRight(int topni, int dir) {
        int[][] dTopnis = new int[T][8];
        // 자기 회전
        if (dir == 1) {
            clockRotate(dTopnis, topni);
        } else {
            noneClockRotate(dTopnis, topni);
        }
        // 오른쪽 연쇄적으로 회전
        while (topni < T - 1) {
            if (topnis[topni][2] == topnis[topni + 1][6]) { // 같은 극이면 회전 x
                break;
            } else { // 다른 극이면 회전
                dir = -dir;
                if (dir == 1) { // 시계
                    clockRotate(dTopnis, topni + 1);
                } else { // 반시계
                    noneClockRotate(dTopnis, topni + 1);
                }
            }
            topni++;
        }
        return dTopnis;
    }

    static int[][] goLeft(int topni, int dir, boolean isDouble) {
        int[][] dTopnis = new int[T][8];
        // 자기 회전
        if (!isDouble) {
            if (dir == 1) {
                clockRotate(dTopnis, topni);
            } else {
                noneClockRotate(dTopnis, topni);
            }
        }

        // 왼쪽 연쇄적으로 회전
        while (topni > 0) {
            if (topnis[topni][6] == topnis[topni - 1][2]) { // 같은 극이면 회전 x
                break;
            } else { // 다른 극이면 회전
                dir = -dir;
                if (dir == 1) { // 시계
                    clockRotate(dTopnis, topni + 1);
                } else { // 반시계
                    noneClockRotate(dTopnis, topni + 1);
                }
            }
            topni--;
        }
        return dTopnis;
    }

    static void clockRotate(int[][] dTopnis, int topni) {
        int last = topnis[topni][7];
        for (int i = 0; i < 7; i++) {
            dTopnis[topni][i + 1] = topnis[topni][i];
        }
        dTopnis[topni][0] = last;
    }

    static void noneClockRotate(int[][] dTopnis, int topni) {
        int first = topnis[topni][0];
        for (int i = 1; i < 8; i++) {
            dTopnis[topni][i - 1] = topnis[topni][i];
        }
        dTopnis[topni][7] = first;
    }

    static int findS() {
        int sum = 0;
        for (int i = 0; i < T; i++) {
            if (topnis[i][0] == 1) {
                sum++;
            }
        }

        return sum;
    }

    // 1 ~ T
    // N : 0
    // S : 1
    // 2, 6 값이 옆 톱니바퀴랑 같은지 다른지
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        topnis = new int[T][8];

        for (int i = 0; i < T; i++) {
            String input = br.readLine();
            for (int j = 0; j < 8; j++) {
                topnis[i][j] = Integer.parseInt(String.valueOf(input.charAt(j)));
            }
        }

        opers = new ArrayList<>();
        K = Integer.parseInt(br.readLine());
        for (int i = 0; i < K; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int topni = Integer.parseInt(st.nextToken()) - 1;
            int dir = Integer.parseInt(st.nextToken());
            opers.add(new Oper(topni, dir));
        }

        for (int i = 0; i < opers.size(); i++) {
            rotate(opers.get(i).topni, opers.get(i).dir);
        }

        ret = findS();

        System.out.println(ret);
    }
}

자신 있게 분기를  잘 나누어서 구현에는 회전로직과 회전여부 판별로직은 작성했는데 이 로직은 Sync의 문제가 생긴다. 즉 회전의 여부를 회전전의 맞닿아 있는 톱니의 극으로 판별하기에 왼쪽먼저 회전했는가 오른쪽 먼저 회전했는가에 따라서 결과가 달라진다.

별 짓거리를 다해보다가 결론은 동시에 돌리지 않으면 정답을 구할 수가 없다. 로 결론이 지어졌다.

---

회전 판별, 회전 로직 보다도 중요한 것은 동시에 돌려야한다는 점이었다. 이를 위해서 각 톱니바퀴의 회전 여부를 포함하는 배열을 선언해서 따로 회전 여부와 방향만 구해준다음 실제 회전은 동시에 진행했다. 아래는 정답 코드이다.

public class Main {

    static int T, K, ret;
    static int[][] topnis;
    static List<Oper> opers;

    static class Oper {
        int topni;
        int dir;

        Oper(int topni, int dir) {
            this.topni = topni;
            this.dir = dir;
        }
    }

    static void rotate(int topni, int dir) {
        int[] dirs = new int[T];
        dirs[topni] = dir;

        // 왼쪽 전파
        for (int i = topni; i > 0; i--) {
            if (topnis[i - 1][2] == topnis[i][6]) {
                break;
            }
            dirs[i - 1] = -dirs[i];
        }

        // 오른쪽 전파
        for (int i = topni; i < T - 1; i++) {
            if (topnis[i + 1][6] == topnis[i][2]) {
                break;
            }
            dirs[i + 1] = -dirs[i];
        }

        for (int i = 0; i < T; i++) {
            if (dirs[i] == -1) {
                noneClockRotate(i);
            } else if (dirs[i] == 1) {
                clockRotate(i);
            }
        }
    }


    static void clockRotate(int topni) {
        int last = topnis[topni][7];
        for (int i = 7; i > 0; i--) {
            topnis[topni][i] = topnis[topni][i - 1];
        }
        topnis[topni][0] = last;
    }

    static void noneClockRotate(int topni) {
        int first = topnis[topni][0];
        for (int i = 1; i < 8; i++) {
            topnis[topni][i - 1] = topnis[topni][i];
        }
        topnis[topni][7] = first;
    }

    static int findS() {
        int sum = 0;
        for (int i = 0; i < T; i++) {
            if (topnis[i][0] == 1) {
                sum++;
            }
        }

        return sum;
    }

    // 1 ~ T
    // N : 0
    // S : 1
    // 2, 6 값이 옆 톱니바퀴랑 같은지 다른지
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        topnis = new int[T][8];

        for (int i = 0; i < T; i++) {
            String input = br.readLine();
            for (int j = 0; j < 8; j++) {
                topnis[i][j] = Integer.parseInt(String.valueOf(input.charAt(j)));
            }
        }

        opers = new ArrayList<>();
        K = Integer.parseInt(br.readLine());
        for (int i = 0; i < K; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int topni = Integer.parseInt(st.nextToken()) - 1;
            int dir = Integer.parseInt(st.nextToken());
            opers.add(new Oper(topni, dir));
        }

        for (int i = 0; i < opers.size(); i++) {
            rotate(opers.get(i).topni, opers.get(i).dir);
        }

        ret = findS();

        System.out.println(ret);
    }
}

마무리하며

시뮬레이션 문제를 풀 때 마다 느끼는 건 문제마다 회전, 비교, 교체 등등 여러가지 요구사항이 주어지는데, 이것을 한번에 하면 굉장히 복잡해진다는 것이다!!

"상태 결정" 과 "상태 반영"을 분리하면 정말 로직이 깔끔해진다. 나는 회전 여부 판별과 실제 회전을 동시에 하려고 했기에 풀이가 미궁속으로 빠졌다.

앞으로도 욕심내서 모든걸 한 메서드에 모으려고 하지말고, 생각을 분리해서 각 분기에 필요한 로직이 무엇인지를 잘 설계해서 문제 풀이에 들어가자. 파이팅 🔥