사다리 조작

📍 문제 설명

 

💡 접근

문제 이해하는데 시간이 꽤나 소요됐다. 가로선을 0~3번까지 추가하여 모든 지점에 대해서 가로선을 만들어 보는 완전탐색 & 백트래킹 문제 였다. 

재귀 호출시 1,1 x,y 지점 모두 가능하나 i,j라고 했을땐 오답이 나온다.

ex) 추가해야할 가로선 갯수 2 i = 1, j = 3이라고 하면

1,3 1,4 가로선 설치가능 여부 확인 부 2,1로 가는게 아니라 2,3 2,4 를 확인하기 때문에!

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, h, k, answer;
    static int[][] board,dis;
    static int[] ch,pm, combi;
    static boolean[] visited;
    static boolean flag = false;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt(); //세로선의 갯수 5
        m = kb.nextInt(); //가로선의 갯수 5
        h = kb.nextInt(); //세로선 마다 가로선을 놓을 수 있는 갯수 6
        board = new int[h+1][n+1];
        for(int i = 0; i < m; i++) {
            int x = kb.nextInt();
            int y = kb.nextInt();
            board[x][y] = 1;
            board[x][y+1] = 2;
        }
        //세로선을 0~3개 까지 추가해본다.
        for(int i = 0; i <= 3; i++) {
            System.out.println("추가해야할 가로선의 갯수는 : " + i + "개 입니다.");
            //추가해야할 가로선의 갯수
            answer = i;
            //세로선 시작점,추가한 가로선의 갯수
            T.solution(1, 1, 0);
            if(flag) break;
        }
        System.out.println(flag ? answer : -1);
    }


    static void solution(int x, int y, int count) {
        if(flag) {
            return;
        }
        //가로선을 모두 추가했으면 i번 출발 i번 도착 확인
        if(answer == count) {
            if(check()) flag = true;
            return;
        }

        //가로선 추가하기
        for(int i = x; i <= h; i++) {
            for(int j = y; j < n; j++) {
                //연결된 가로선이 없으면 가로선 추가
                if(board[i][j] == 0 && board[i][j+1] == 0) {
                    board[i][j] = 1;
                    board[i][j+1] = 2;
                    System.out.println("(" + i + ", " + j + ") 좌표에 +1열 까지 가로선 추가했습니다.");
                    solution(1, 1, count +1);
                    System.out.println("확인이 끝났으니 가로선 없앱니다.");
                    //추가한 가로선을 다시 제거한다.
                    board[i][j] = 0;
                    board[i][j+1] = 0;
                }
            }
        }

    }

    //i번 출발 i번 도착이 맞는지 확인하는 메서드
    private static boolean check() {
        for(int i = 1; i <= n; i++) {
            //행
            int nx = 1;
            //열
            int ny = i;

            //끝행까지 탐색
            while (nx <= h) {
                if(board[nx][ny] == 1) ny++; // 우측 이동
                else if (board[nx][ny] == 2) ny--; // 좌측 이동
                nx++; //
            }
            //i번의 도착지점 확인
            if(ny != i) return false;
        }
        return true;
    }


}