15684 사다리 조작 (Java)

(15684) 사다리 조작

🌍TISTORY

문제 🌐

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N=5, H=6인 경우의 그림이고, 가로선은 없다.

초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.

위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.

사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다. 이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다.

위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다. 아래 두 그림은 1번과 2번이 어떻게 이동했는지 나타내는 그림이다.

1번 세로선

2번 세로선

 

사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때, i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세로선의 개수 N, 가로선의 개수 M, 세로선마다 가로선을 놓을 수 있는 위치의 개수 H가 주어진다. (2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N-1)×H)

둘째 줄부터 M개의 줄에는 가로선의 정보가 한 줄에 하나씩 주어진다.

가로선의 정보는 두 정수 a과 b로 나타낸다. (1 ≤ a ≤ H, 1 ≤ b ≤ N-1) b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.

가장 위에 있는 점선의 번호는 1번이고, 아래로 내려갈 때마다 1이 증가한다. 세로선은 가장 왼쪽에 있는 것의 번호가 1번이고, 오른쪽으로 갈 때마다 1이 증가한다.

입력으로 주어지는 가로선이 서로 연속하는 경우는 없다.

출력

i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력한다. 만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다.

 

접근 방법

사다리 입력받기

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int H = sc.nextInt();

        // 행 0번: 시작 행 H+1번: 끝
        int[][] ladder = new int[H+2][N+1];
        for (int i=0; i<M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            // 옆구리 이동 방향으로 1, -1 (막대가 양쪽으로 연결되기 때문에 +-1 로 했어요)
            ladder[a][b] = 1;
            ladder[a][b+1] = -1;
        }

사다리는 두 개의 세로줄에 양방향으로 연결되기 때문에 i번째 줄 기준으로 오른쪽에 줄이 그어졌다면 i+1 줄에도 왼쪽으로 그어져야 한다. 그래서 i번째 기준으로 오른쪽일 때 i인덱스에 1을, i+1 인덱스에 -1을 넣었다.

줄을 0개부터 3개까지 그어 보고 정답이 나오면 바로 반복문 빠져나오기, 그렇지 않으면 계속 확인함.

        for (int i=0; i<=3; i++) {
            if (dfs(i, 0, ladder, N, H)) {
                answer = i;
                break;
            }
        }

 

사다리에 줄 긋기

조합을 하나씩 다 구해보고 사다리에 추가한 후에 돌리려고 생각했다. 하지만 그렇게 하면 시간 초과 이슈로 정답 근처에도 못 갈 거라는 피드백을 듣고… dfs에 사다리 배열을 인자로 넘겨주고, 그 안에서 ladderCheck 메소드에 넣어서 확인하는 방식으로 구현했다.

일차원 배열의 경우 조합을 만들 때 index를 가지고 다음 인덱스를 지속적으로 넘겨줘서 중복 확인을 하지 않도록 코드를 짠다. 하지만 이 문제의 경우 중복 확인이 일어나도 문제의 제한 시간을 초과하지 않기 때문에 그냥 사다리 배열만 확인했다.

참고로 이차원 배열은 인덱스를 누적값으로 가지고 있다가 index/열 과 index%열 로 현재 위치를 확인한다.

    // 조합을 구하는 dfs
    // 그런데 이차원 배열에서 조합 구하는 것이 index로 하는 방법도 있다는데... (나중에)
    static boolean dfs(int depth, int cnt, int[][] ladder, int N, int H) {
        // 지금까지 그은 줄의 개수 == 내가 긋고 싶은 줄의 개수
        if (cnt == depth) {
            // ladderCheck 하기
            return ladderCheck(ladder, N, H);
        } else {
            for (int r=1; r<=H; r++) {
                for (int c=1; c<N; c++) {
                    if (ladder[r][c] == 0 && ladder[r][c+1]==0) {
                        ladder[r][c] = 1;
                        ladder[r][c+1]=-1;
                        // 날 힘들게 한...
                        // 여기서 dfs의 결과가 true면 true를 보내준다
                        boolean temp = dfs(depth, cnt+1, ladder, N, H);
                        if (temp) return true;
                        ladder[r][c]=0;
                        ladder[r][c+1]=0;
                    }
                }
            }
        }
        return false;
    }

여기서 temp = dfs 를 해주지 않아 true 값이 리턴되지 않았던 이슈가 있었다… 휴……

 

조건에 맞는 사다리인지 판별하기

1번 사다리부터 N번 사다리까지 밑으로 내려간다. 여기서 N-1 까지만 돌려도 된다!! 어차피 마지막 하나는 값이 정해지기 때문에.

결과값 result를 true로 설정해 두고, 조건에 맞지 않을 경우 false로 변경하고 반복문을 빠져나왔다.

사다리에 연결 상태를 판별할 때 방향을 구분하기 위해 1, -1로 값을 확인했다.

    static boolean ladderCheck(int[][] ladder, int N, int H) {
        boolean result = true;
        // 시작 위치 1번부터 N번까지
        for (int i=1; i<=N; i++) {
            // 1번 행부터 시작하고
            int r=1;
            // i번 열부터 시작
            int c=i;
            // 현재 위치가 H를 벗어나면 while 문을 빠져나온다
            while (r<H+1) {
                // 현재 위치에서 값이 1이거나 -1이면 옆으로 움직인다
                if (ladder[r][c] == 1) c++;
                else if (ladder[r][c] == -1) c--;
                // 그리고 한칸 아래로 가기
                r++;
            }
            if (c!=i) {
                // 만약 다 내려온 후에 원래 시작점 i와 c가 다르다면 사다리가 말이 안 된다는 뜻이므로 결과에 false, break
                result = false;
                break;
            }
        }
        return result;
    }

Full Solution

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

public class B15684 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int H = sc.nextInt();

        // 행 0번: 시작 행 H+1번: 끝
        int[][] ladder = new int[H+2][N+1];
        for (int i=0; i<M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            // 옆구리 이동 방향으로 1, -1 (막대가 양쪽으로 연결되기 때문에 +-1 로 했어요)
            ladder[a][b] = 1;
            ladder[a][b+1] = -1;
        }

        int answer = -1;

        // dfs 했어요.
        // 0개를 그을 때~3개를 그을 때
        for (int i=0; i<=3; i++) {
            // 그었을 때 사다리가 조건에 맞으면 벗어나고 답을 초기화하기
            if (dfs(i, 0, ladder, N, H)) {
                answer = i;
                break;
            }
        }

        System.out.println(answer);

    }


    // 조합을 구하는 dfs
    // 그런데 이차원 배열에서 조합 구하는 것이 index로 하는 방법도 있다는데... (나중에)
    static boolean dfs(int depth, int cnt, int[][] ladder, int N, int H) {
        // 지금까지 그은 줄의 개수 == 내가 긋고 싶은 줄의 개수
        if (cnt == depth) {
            // ladderCheck 하기
            return ladderCheck(ladder, N, H);
        } else {
            for (int r=1; r<=H; r++) {
                for (int c=1; c<N; c++) {
                    if (ladder[r][c] == 0 && ladder[r][c+1]==0) {
                        ladder[r][c] = 1;
                        ladder[r][c+1]=-1;
                        // 날 힘들게 한...
                        // 여기서 dfs의 결과가 true면 true를 보내준다
                        boolean temp = dfs(depth, cnt+1, ladder, N, H);
                        if (temp) return true;
                        ladder[r][c]=0;
                        ladder[r][c+1]=0;
                    }
                }
            }

        }

        return false;
    }

    static boolean ladderCheck(int[][] ladder, int N, int H) {
        boolean result = true;
        // 시작 위치 1번부터 N번까지
        for (int i=1; i<=N; i++) {
            // 1번 행부터 시작하고
            int r=1;
            // i번 열부터 시작
            int c=i;
            // 현재 위치가 H를 벗어나면 while 문을 빠져나온다
            while (r<H+1) {
                // 현재 위치에서 값이 1이거나 -1이면 옆으로 움직인다
                if (ladder[r][c] == 1) c++;
                else if (ladder[r][c] == -1) c--;
                // 그리고 한칸 아래로 가기
                r++;
            }
            if (c!=i) {
                // 만약 다 내려온 후에 원래 시작점 i와 c가 다르다면 사다리가 말이 안 된다는 뜻이므로 결과에 false, break
                result = false;
                break;
            }
        }
        return result;
    }

}