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

 

www.acmicpc.net/problem/15684

15684번: 사다리 조작

 

풀이 아이디어

 

놓을 수 있는 사다리 위치에 사다리를 하나씩 놓아보고 그때마다 사다리 게임을 돌려 확인하는 방식으로 풀 수 있습니다.

사실 말이 쉽지, 꽤 까다로웠습니다. 구현 문제는 정말 너무 어려운 것 같네요.

 

가중 중요하게 신경써야될 한 가지 포인트만 소개하겠습니다.

 

putLadderDown의 재귀 방식

putLadderDown 메서드 안에는 이중 for문이 있습니다.

놓을 수 있는 위치에 사다리를 놓고, 카운트를 센 다음 재귀로 넘어가게 돼있는데

이때 다음 재귀함수에서 사다리를 찾을 수 있는 범위를 줄여주는게 중요합니다.

 

단순하게 0에서 시작해 처음부터 이중 for문을 돌아버리면 시간초과가 발생합니다.

저는 row index를 넘기면서 재귀로 넘기면서 row의 범위를 줄였지만, column을 줄여도 상관없습니다.

 

 

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N,M,H;
    static boolean[][] adj;
    static boolean[][] visited;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception{
//        BufferedReader br = new BufferedReader(new FileReader("testcase.txt"));
        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());

        adj = new boolean[H][N-1];
        visited = new boolean[H][N-1];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            adj[a][b] = true;
        }
        putLadderDown(0,0);

        System.out.println(min == Integer.MAX_VALUE ? -1 : min);
    }

    private static void putLadderDown(int h, int ladder) {
        if(ladder > 3) {
            return;
        }
        if(simulate()) {
            min = Math.min(min, ladder);
        };

        for (int i = h; i < H; i++) {
            for (int j = 0; j < N-1; j++) {
                if(isValidPosition(i,j) && !visited[i][j]) {
                    visited[i][j] = true; adj[i][j] = true;
                    putLadderDown(i,ladder + 1);
                    visited[i][j] = false; adj[i][j] = false;
                }
            }
        }
    }

    private static boolean simulate() {
        for (int i = 0; i < N; i++) {
            int dest = go(i);
            if(dest != i) return false;
        }
        return true;
    }


    private static int go(int start) {
        int h = 0;
        int n = start;

        while(true) {
            if(h == H) return n;

            if(n == N-1) {
                if(adj[h][n-1]) {
                    n--;
                }
                h++;
                continue;
            }

            if(adj[h][n]) {
                n++;  h++;
                continue;
            }
            if(n > 0 && adj[h][n-1]) {
                n--;  h++;
                continue;
            }
            h++;
        }
    }


    private static boolean isValidPosition(int row, int col) {
        boolean hasLeftLine = col-1 > 0 && adj[row][col-1];

        boolean hasRightLine = adj[row][col];
        boolean hasRightJumpLine = col+1 < N-1 && adj[row][col+1];

        if(hasLeftLine || hasRightLine || hasRightJumpLine) return false;
        return true;
    }


}