[JAVA] 백준 15684 사다리 조작

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

15684번: 사다리 조작

 

풀이 후기

- 인덱스 처리가 힘들었다. 원래는 사다리 크기에 딱 맞는 배열을 생성하여 범위 체크해가며 풀이했는데 코드가 복잡해져서 좌우로 마진을 한칸씩 주고, 범위 체크 없이 좌우에 사다리가 있는지 없는지를 확인했다

- 나는 boolean 배열로 해당 칸에 사다리가 있다 없다를 체크했는데, 다른 코드를 보니 오른쪽으로 뻗은 사다리는 1로 왼쪽으로 뻗은 사다리는 -1로 한 코드가 많았다. 더 직관적일 것 같다

- 사다리를 2차원 배열로 생각하는게 힘들었다.. 

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        map = new boolean[H+1][N+1];
        while(M-->0){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            map[a][b] = true;
        }

        for(int i=0;i<=3;i++){
            comb(0, 0, i);
        }

        System.out.println(-1);
    }

    static int N,M,H;
    static boolean[][] map;

    public static void comb(int idx, int cnt, int n){
        if(cnt==n){
            if(start()){
                System.out.println(n);
                System.exit(0);
            }
            return;
        }

        for (int i = idx; i < (N - 1) * H; i++) {
            int r = i/(N-1)+1;
            int c = i%(N-1)+1;
            if(!map[r][c] && !map[r][c+1] && !map[r][c-1]){
                map[r][c] = true;
                comb(i+1, cnt+1, n);
                map[r][c] = false;
            }
        }
    }

    public static boolean start(){
        for(int i=1;i<=N;i++){
            int line = i;
            for(int j=1;j<=H;j++){
                boolean move = false;
                if(line<N && map[j][line]){
                    line++;
                    move = true;
                }
                if(!move && 0<=line-1 && map[j][line-1]) line--;
            }
            if(line!=i) return false;
        }
        return true;
    }
}