시계맞추기 (ID : CLOCKSYNC)

https://www.algospot.com/judge/problem/read/CLOCKSYNC

algospot.com :: CLOCKSYNC

 

 

처음에 문제를 읽고나서 풀기가 굉장히 어렵다고 생각되었던 부분이 현재 '12시' 로 맞춰져있는 시계를 다시 변경해서 답을 찾아가야하는지에 대한 부분이었다. 이렇게 이미 '12시'로 맞춰져 있는 시계를 건드리게 되면 답을 얻기 위해 따져봐야하는 경우의 수가 기하급수적으로 증가해버리기 때문이다. 그래서 일단은 예제에 나와있는대로 종이와 펜을 들고 그려가면서 시뮬레이션을 해보기로 했다. 오 그런데 이게 왠걸! 특정 스위치로만 맞출 수 있는 시계가 있는 경우가 있었고, 우선적으로 해당 시계를 먼저 '12시' 로 맞춰준 후 다시는 건들지 않으면 되는 방법이 있었다. 또, 특정 스위치로 맞출 수 있는 시계가 두 개인 경우도 있었는데 이 경우도 한 개의 시계인 경우와 마찬가지로 두 시계를 '12시'로 맞춰주고 다시는 건들이 않으면 되었다. 만약 이 두 시계의 시침이 서로 다른 방향을 가리킨다면 절대 두 시계가 '12시'를 가리킬 수 없기 때문에 문제를 풀기 불가능한 상황이 되어 -1을 리턴하면 되었다.

 

이런식으로 스위치를 다시 살펴보니 모든 시계를 12시를 바라보도록 하기 위한 필연적인 순서가 있었고 이는 다음과 같았다.

4번 스위치 (6, 7, 8, 10, 12) : 8, 12 고정
2번 스위치 (4, 10, 14, 15) : 10 고정
9번 스위치 (3, 4, 5, 9, 13) : 13 고정
1번 스위치 (3, 7, 9, 11) : 9, 11 고정
3번 스위치 (0, 4, 5, 6, 7) : 6 고정
7번 스위치 (4, 5, 7, 14, 15) : 7고정
8번 스위치 (1, 2, 3, 4, 5) : 4, 5 고정
6번 스위치 (3, 14, 15) : 3 고정
0번 스위치 (0, 1, 2) : 1 고정
5번 스위치 (0, 2, 14, 15) : 네 방향 확인

 

위 순서를 따라가면서 코드를 작성하여 제출했더니, 알고스팟의 문제를 풀기 시작한 이후 처음으로 '정답'을 받아봤다. 😭

 

답안 제출한 코드는 아래와 같다.

import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static List<List<Integer>> clockChain = Arrays.asList(
            Arrays.asList(0, 1, 2),
            Arrays.asList(3, 7, 9, 11),
            Arrays.asList(4, 10, 14, 15),
            Arrays.asList(0, 4, 5, 6, 7),
            Arrays.asList(6, 7, 8, 10, 12),
            Arrays.asList(0, 2, 14, 15),
            Arrays.asList(3, 14, 15),
            Arrays.asList(4, 5, 7, 14, 15),
            Arrays.asList(1, 2, 3, 4, 5),
            Arrays.asList(3, 4, 5, 9, 13)
    );

    public static void main(String[] args) {
//        String filePath = "clocksync/input.txt";
//        InputStream inputStream = Main.class.getClassLoader().getResourceAsStream(filePath);
//        Scanner scanner = new Scanner(inputStream);
        Scanner scanner = new Scanner(System.in);

        int caseCount = Integer.parseInt(scanner.nextLine());
        for (int cc = 0; cc < caseCount; cc++) {
            int[][] clockBoard = new int[4][4];

            String[] hours = scanner.nextLine().trim().split(" ");
            for (int i = 0; i < 16; i++) {
                clockBoard[i / 4][i % 4] = Integer.parseInt(hours[i]);
            }

            System.out.println(program(clockBoard));
        }
    }

    public static int program(int[][] clockBoard) {
        // 모든 시계가 12시 방향으로 정렬된 경우
        if(isFinish(clockBoard)) {
            return 0;
        }

        int click = 0;

        // 4번 스위치 (6, 7, 8, 10, 12) > 8, 12 고정
        if(clockBoard[2][0] != clockBoard[3][0]) {
            return -1;
        } else {
            if(clockBoard[2][0] != 12) {
                int result = getClickCountByTwoClock(clockBoard, 4, 2, 0, 3, 0);
                if(result == -1) {
                    return -1;
                } else {
                    click += result;
                }
            }
        }

        // 2번 스위치 (4, 10, 14, 15) > 10 고정
        if(clockBoard[2][2] != 12) {
            int result = getClickCountByOneClock(clockBoard, 2, 2, 2);
            if(result == -1) {
                return -1;
            } else {
                click += result;
            }
        }

        // 9번 스위치 (3, 4, 5, 9, 13) > 13 고정
        if(clockBoard[3][1] != 12) {
            int result = getClickCountByOneClock(clockBoard, 9, 3, 1);
            if(result == -1) {
                return -1;
            } else {
                click += result;
            }
        }

        // 1번 스위치 (3, 7, 9, 11) > 9, 11 고정
        if(clockBoard[2][1] != clockBoard[2][3]) {
            return -1;
        } else {
            if(clockBoard[2][1] != 12) {
                int result = getClickCountByTwoClock(clockBoard, 1, 2, 1, 2, 3);
                if(result == -1) {
                    return -1;
                } else {
                    click += result;
                }
            }
        }

        // 3번 스위치 (0, 4, 5, 6, 7) > 6 고정
        if(clockBoard[1][2] != 12) {
            int result = getClickCountByOneClock(clockBoard, 3, 1, 2);
            if(result == -1) {
                return -1;
            } else {
                click += result;
            }
        }

        // 7번 스위치 (4, 5, 7, 14, 15) > 7고정
        if(clockBoard[1][3] != 12) {
            int result = getClickCountByOneClock(clockBoard, 7, 1, 3);
            if(result == -1) {
                return -1;
            } else {
                click += result;
            }
        }

        // 8번 스위치 (1, 2, 3, 4, 5) > 4, 5 고정
        if(clockBoard[1][0] != clockBoard[1][1]) {
            return -1;
        } else {
            if(clockBoard[1][0] != 12) {
                int result = getClickCountByTwoClock(clockBoard, 8, 1, 0, 1, 1);
                if(result == -1) {
                    return -1;
                } else {
                    click += result;
                }
            }
        }

        // 6번 스위치 (3, 14, 15) > 3 고정
        if(clockBoard[0][3] != 12) {
            int result = getClickCountByOneClock(clockBoard, 6, 0, 3);
            if(result == -1) {
                return -1;
            } else {
                click += result;
            }
        }

        // 0번 스위치 (0, 1, 2) > 1 고정
        if(clockBoard[0][1] != 12) {
            int result = getClickCountByOneClock(clockBoard, 0, 0, 1);
            if(result == -1) {
                return -1;
            } else {
                click += result;
            }
        }

        // 5번 스위치 (0, 2, 14, 15) > 네 방향 확인
        if(isFinish(clockBoard)) {
            return click;
        }

        boolean is5SwitchClear = false;

        for(int i = 0; i < 4; i++) {
            if(is5SwitchClear) {
                break;
            }

            List<Integer> clockIndexes = clockChain.get(5);

            click++;
            for (int clockIndex : clockIndexes) {
                clockBoard[clockIndex / 4][clockIndex % 4] += 3;
                if (clockBoard[clockIndex / 4][clockIndex % 4] == 15) {
                    clockBoard[clockIndex / 4][clockIndex % 4] = 3;
                }

                if(clockBoard[0][0] == 12 && clockBoard[0][2] == 12 && clockBoard[3][2] == 12 && clockBoard[3][3] == 12) {
                    is5SwitchClear = true;
                    break;
                }
            }

            if(isFinish(clockBoard)) {
                return click;
            }
        }

        if(!is5SwitchClear) {
            return -1;
        }

        return click;
    }

    public static boolean isFinish(int[][] clockBoard) {
        for (int i = 0; i < 16; i++) {
            if (clockBoard[i / 4][i % 4] != 12) {
                return false;
            }
        }
        return true;
    }

    public static int getClickCountByOneClock(int[][] clockBoard, int switchIndex, int trow, int tcol) {
        int click = 0;
        boolean isClear = false;

        for(int i = 0; i < 4; i++) {
            if(isClear) {
                break;
            }

            List<Integer> clockIndexes = clockChain.get(switchIndex);

            click++;
            for (int clockIndex : clockIndexes) {
                clockBoard[clockIndex / 4][clockIndex % 4] += 3;
                if (clockBoard[clockIndex / 4][clockIndex % 4] == 15) {
                    clockBoard[clockIndex / 4][clockIndex % 4] = 3;
                }

                if(clockBoard[trow][tcol] == 12) {
                    isClear = true;
                }
            }

            if(isFinish(clockBoard)) {
                return click;
            }
        }

        if(!isClear) {
            return -1;
        }

        return click;
    }

    public static int getClickCountByTwoClock(int[][] clockBoard, int switchIndex, int trow1, int tcol1, int trow2, int tcol2) {
        int click = 0;
        boolean isClear = false;

        for(int i = 0; i < 4; i++) {
            if(isClear) {
                break;
            }

            List<Integer> clockIndexes = clockChain.get(switchIndex);

            click++;
            for (int clockIndex : clockIndexes) {
                clockBoard[clockIndex / 4][clockIndex % 4] += 3;
                if (clockBoard[clockIndex / 4][clockIndex % 4] == 15) {
                    clockBoard[clockIndex / 4][clockIndex % 4] = 3;
                }

                if(clockBoard[trow1][tcol1] == 12 && clockBoard[trow2][tcol2] == 12) {
                    isClear = true;
                }
            }

            if(isFinish(clockBoard)) {
                return click;
            }
        }

        if(!isClear) {
            return -1;
        }

        return click;
    }

 

재귀호출을 사용한 완전탐색 풀이

알고리즘 문제해결 전략 책을 통해 확인한 답안 코드는 재귀함수를 이용한 완전탐색 풀이법이었다. 나는 주어진 조건들을 이용해서 답이 발생할 수 있는 루트를 직접 계산에서 코드로 구현했다면 재귀함수는 모든 가능한 경우를 탐색하는 방법으로 문제 의도에 더 적합한 풀이법이라는 생각이 들었다. 재귀 코드가 매우 멋있다.

 

import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static final int INF = 9999;
    public static final int SWITCHES = 10;
    public static final int CLOCKS = 16;

    // linked[i][j] = 'x': i번 스위치와 j번 시계가 연결되어 있다.
    // linked[i][j] = '.': i번 스위치와 j번 시계가 연결되어 있지 않다.
    public static List<String> clockChain = Arrays.asList(
            // 0123456789012345
            "xxx.............",
            "...x...x.x.x....",
            "....x.....x...xx",
            "x...xxxx........",
            "......xxx.x.x...",
            "x.x...........xx",
            "...x..........xx",
            "....xx.x......xx",
            ".xxxxx..........",
            "...xxx...x...x.."
    );
    public static void main(String[] args) {
//        String filePath = "clocksync/input.txt";
//        InputStream inputStream = Main.class.getClassLoader().getResourceAsStream(filePath);
//        Scanner scanner = new Scanner(inputStream);
        Scanner scanner = new Scanner(System.in);

        int caseCount = Integer.parseInt(scanner.nextLine());
        for (int cc = 0; cc < caseCount; cc++) {
            int[][] clockBoard = new int[4][4];

            String[] hours = scanner.nextLine().trim().split(" ");
            for (int i = 0; i < 16; i++) {
                clockBoard[i / 4][i % 4] = Integer.parseInt(hours[i]);
            }

            int result = solve(clockBoard, 0);
            System.out.println(result == INF ? -1 : result);
        }
    }

    // 모든 시계가 12시를 가리키고 있는지 확인한다.
    public static boolean areAligned(int[][] clockBoard) {
        for (int i = 0; i < 16; i++) {
            if (clockBoard[i / 4][i % 4] != 12) {
                return false;
            }
        }
        return true;
    }

    // 스위치를 누른다.
    public static void push(int[][] clockBoard, int switchIndex) {
        for (int clock = 0; clock < CLOCKS; clock++) {
            if (clockChain.get(switchIndex).charAt(clock) == 'x') {
                clockBoard[clock / 4][clock % 4] += 3;
                if (clockBoard[clock / 4][clock % 4] == 15) {
                    clockBoard[clock / 4][clock % 4] = 3;
                }
            }
        }
    }

    // clocks: 현재 시계들의 상태
    // switchIndex: 이번에 누를 스위치 번호
    // 가 주어질 때 남은 스위치들을 눌러서 clocks 를 12시로 맞출 수 있는 최소 횟수를 반환한다.
    // 만약 불가능하다면 INF 이상의 큰 수를 반환한다.
    public static int solve(int[][] clockBoard, int switchIndex) {
        if (switchIndex == SWITCHES) {
            return areAligned(clockBoard) ? 0 : INF;
        }

        // 이 스위치를 0번 누르는 경우부터 세 번 누르는 경우까지를 모두 시도한다.
        int ret = INF;
        for (int cnt = 0; cnt < 4; cnt++) {
            ret = Math.min(ret, cnt + solve(clockBoard, switchIndex + 1));
            push(clockBoard, switchIndex);
        }

        // push(clocks, switch)가 네 번 호출되었으니 clocks는 원래와 같은 상태가 된다.
        return ret;
    }
}