[java]사다리 조작 - 백준15684

문제

• 사다리 조작(백준15684)

풀이

문제 해석을 하자면,

• 주어진 문제는 사다리타기 게임을 진행하여 선택한 번호와 결과 번호가 동일한 경우를 구하는 문제이다.
• 문제를 잘 해석해보면 어려울 건 없고, 단순한 구현 문제이다.

풀이

• 복잡도가 크지 않아 완전탐색으로 단순 “구현”을 생각하자
• 아래와 같이 2가지 함수를 만들어서 구현하자
  • (1) 완전 탐색으로 재귀(dfs)를 너비 NXH 가지수, 높이 3 으로 생각한 것이 “핵심”
    • dfs -> 2중 for문으로 완전탐색을 하자 (백트래킹 활용) + 연속 가로선 체크!
    • visited 를 통해 “가로선 삽입”
  • (2) runFun -> 사다리 타기 게임 함수 (좌표와 범위를 조심해서 구현)

코드

public static int N, M, H;
public static int result = Integer.MAX_VALUE;
public static boolean[][] visited = new boolean[33][13];
public static int[][] outArr = new int[5][2]; // debug

public static void runFun(int count) {
    boolean check = true;
    int curH = -1;
    int curW = -1;
    for(int i=1; i<=N; i++) {
        curW = i;
        curH = 1; //init
        while(true) {
            //end point
            if(curH == H+1) break;
            if(visited[curH-1][curW-1]) { // 오른쪽 가로선
                curH++;
                curW++;
                continue;
            }else if(!(curW-2<0) && visited[curH-1][curW-2]) { // 왼쪽 가로선
                curH++;
                curW--;
                continue;
            }
            // 가로선 없는 상황 이라면,
            curH++;
        }
        if(curW != i) {
            check = false;
            break; //바로 탈출(더 확인할 필요가 없음)
        }
    }

    if(check) {
        result = Math.min(result, count);
    }
}

public static void dfs(int depth) {
    // 사다리 타기 게임 결과 함수
    runFun(depth);

    //base condition
    if(depth == 3) {
        // debug
        //			for(int i=1; i<=3; i++) {
        //				System.out.print(outArr[i][0]+","+outArr[i][1]+" ");
        //			}
        //			System.out.println();
        return;
    }
    //recursion
    for(int i=0; i<H; i++) {
        for(int j=0; j<N-1; j++) {
            if(visited[i][j]) continue;
            // 연속 가로선인지 검증작업 필요
            if(j-1 > 0 && j+1 < N) {
                if(visited[i][j-1] || visited[i][j+1]) continue;	
            }
            visited[i][j] = true; //가로선 추가
            outArr[depth+1][0] = i;
            outArr[depth+1][1] = j;
            dfs(depth+1);
            visited[i][j] = false;
        }
    }
}

public static void main(String[] args) throws Exception {
    //init -> 백준 생략
    //input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(stk.nextToken());
    M = Integer.parseInt(stk.nextToken());
    H = Integer.parseInt(stk.nextToken());
    for(int i=0; i<M; i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        int a = Integer.parseInt(stk.nextToken());
        int b = Integer.parseInt(stk.nextToken());
        //			inArr[a][b] = 1;
        visited[a-1][b-1] = true; //입력 가로선 추가
    }
    //run
    //		visited[3][1]=true;
    //		visited[0][2]=true;
    //		visited[2][3]=true;

    //		visited[5][1]=true;
    //		visited[4][3]=true;
    //		runFun(2);
    dfs(0);
    //output
    if(result > 3) result = -1;
    System.out.println(result);
}

느낀점

생략