[백준 | Java] 15684번 사다리 조작

문제

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

15684번: 사다리 조작

티어

소요 시간

1시간 2분

분류

구현

백트래킹

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {

    static int n, h;
    static int[][] ladders;
    static int minCnt = 4;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = line[0]; h = line[2];
        int m = line[1];
        ladders = new int[n + 1][h + 1];
        for (int i = 0; i < m; i++) {
            line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            ladders[line[1]][line[0]] = line[1] + 1;
            ladders[line[1] + 1][line[0]] = line[1];
        }

        if (line[1] == 0) bw.write(Integer.toString(0));
        else {
            makeLadder(1, 0);
            if (minCnt > 3) minCnt = -1;
            bw.write(Integer.toString(minCnt));
        }
        bw.flush();
    }

    private static void makeLadder(int b, int cnt) {
        if (checkLadderGame()) {
            minCnt = Math.min(minCnt, cnt);
        }
        if (cnt < 3) {
            for (int i = b; i < n; i++) {
                for (int j = 1; j <= h; j++) {
                    if (ladders[i][j] == 0 && ladders[i + 1][j] == 0) {
                        ladders[i][j] = i + 1;
                        ladders[i + 1][j] = i;
                        makeLadder(i, cnt + 1);
                        ladders[i][j] = 0;
                        ladders[i + 1][j] = 0;
                    }
                }
            }
        }
    }

    private static boolean checkLadderGame() {
        for (int i = 1; i <= n; i++) {
            if (!checkEachLadder(i)) return false;
        }
        return true;
    }

    private static boolean checkEachLadder(int vertical) {
        int curX = vertical;
        for (int curY = 1; curY <= h; curY++) {
            if (ladders[curX][curY] != 0) curX = ladders[curX][curY];
        }

        if (curX == vertical) return true;
        else return false;
    }
}

코드 설명

접근방법과 풀이를 빨리 캐치해서 30분 내에 풀 수 있을 줄 알았지만 백트래킹을 2중으로 하면서 실수를 하는 바람에 디버깅만 30분을 더했다🫠

 

2초라는 넉넉한 시간 때문에 백트래킹으로 진행했다.

그리디로 풀 수 있을까 싶었는데 알고리즘 자체가 복잡해질 것 같았고 시간이 넉넉했기 때문에 시도하지 않았다.

 

실수한 부분은 가로, 세로를 파라미터로 받는 백트래킹 함수에서 내부 for문이다.

private static void makeLadder(int b, int cnt) {
    if (checkLadderGame()) {
        minCnt = Math.min(minCnt, cnt);
    }
    if (cnt < 3) {
        for (int i = b; i < n; i++) {
            for (int j = 1; j <= h; j++) {
                if (ladders[i][j] == 0 && ladders[i + 1][j] == 0) {
                    ladders[i][j] = i + 1;
                    ladders[i + 1][j] = i;
                    makeLadder(i, cnt + 1);
                    ladders[i][j] = 0;
                    ladders[i + 1][j] = 0;
                }
            }
        }
    }
}

 

ladders 변수는 사다리 가로선을 의미한다.

ladders[i][j] = i + 1의 경우 세로 선 i, 가로 선 j에서 시작하는 가로선이 세로 선 i + 1을 잇는다는 말이다.

 

for문의 경우 외부 for문은 세로 선을, 내부 for문의 경우 가로 선을 의미한다.

가로선 (내부 for문)의 경우 1부터 시작하는 이유는 a라는 파라미터를 두고 a부터 시작할 경우 같은 층계만을 계속해서 구하기 때문에 답이 잘 구해지지 않는다.

예를 들어 a, b가 3, 6일 경우 다음 재귀에 들어갔을 때 for문은 (4, 6), (5, 6) ... 이런 식으로 같은 층의 가로선만 검증을 하게 된다.

하지만 살펴봐야할 곳은 (4, 1), (4, 2), (4, 3) ... (5, 6)이기 때문에 내부 for문의 경우 파라미터를 따로 두지 않고 1부터 검증하는 코드를 작성했다.

 

더 리팩토링 할 수 있는 방법은 for문의 순서를 바꾸고 최적화를 하는 것이다.

같은 층계를 먼저 살펴보는 코드를 작성한다면 위와 같이 실수할 일은 없을 것 같다.