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

백준 15684번 사다리 조작 : https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

 

 

 

 

개인적으로 많이 어려웠던 문제다.

처음에는 bfs로 시도해봤지만 배열을 복사하는 탓에 메모리, 시간 초과가 떠서 dfs로 풀게 되었다.

평소에 사용하던 dfs의 방식으로 풀이하여 통과하긴 했지만,

모든 경우의 수를 전부 확인하며 최소값을 찾는 방법이기 때문에 시간이 오래 걸렸다.

 

따라서 이 문제에서는 dfs를 약간 독특하게 변형하여 풀었다.

사다리의 수를 0, 1, 2, 3씩 늘려가며 dfs로 그 이상 탐색을 하면 return 하는 방식으로 체크를 했다.

이 방법으로 하면 만약 사다리의 수를 2개만 놓았을 때 조건에 만족이 된다면,

사다리 3개 놓았을 때의 모든 경우의 수를 체크하지 않아도 된다.

뭔가 dfs로 bfs를 하는 듯 하여 신선했다. 

 

사다리를 놓는 방법은 간단하다.

2차원 int 배열을 선언하여 사다리를 표시하는데, 1이면 오른쪽으로 가고 2면 왼쪽으로 가게 한다.

사다리를 타고 i번 세로선의 결과가 i번이 나와야 하므로, 이를 체크해주는 함수를 작성한다. (check 함수)

각각의 행에서 출발하여 아래로 내려가는데

만약 해당 위치가 1이면 오른쪽으로 한칸 이동하고, 2면 왼쪽으로 한칸 이동한다.

 

 

총 걸린 시간 : 3시간 이상

난이도 : ★★★★☆

 

코드

변형한 dfs (312ms)

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

public class Main {
    private static int n, m, h, answer;
    private static int[][] map;
    private static boolean finish = false;

    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 int[h + 1][n + 1];

        int x, y;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            map[x][y] = 1;
            map[x][y + 1] = 2;
        }

        for (int i = 0; i <= 3; i++) {
            answer = i;
            dfs(1, 0);
            if (finish) break;
        }

        System.out.println((finish) ? answer : -1);
    }

    private static void dfs(int x, int count) {
        if (finish) return;
        if (answer == count) {
            if (check()) finish = true;
            return;
        }

        for (int i = x; i < h + 1; i++) {
            for (int j = 1; j < n; j++) {
                if (map[i][j] == 0 && map[i][j + 1] == 0) {
                    map[i][j] = 1;
                    map[i][j + 1] = 2;
                    dfs(i, count + 1);
                    map[i][j] = map[i][j + 1] = 0;
                }
            }
        }
    }

    private static boolean check() {
        for (int i = 1; i <= n; i++) {
            int x = 1, y = i;
            for (int j = 0; j < h; j++) {
                if (map[x][y] == 1) y++;
                else if (map[x][y] == 2) y--;
                x++;
            }
            if (y != i) return false;
        }
        return true;
    }
}

 

기존에 자주 사용하던 dfs (1016ms)

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

public class Main {
    private static int n, m, h, answer = 4;
    private static int[][] map;

    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 int[h + 1][n + 1];

        int x, y;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            map[x][y] = 1;
            map[x][y + 1] = 2;
        }

        dfs(1, 0);
        System.out.println((answer != 4) ? answer : -1);
    }

    private static void dfs(int x, int count) {
        if (answer <= count) return;
        else {
            if (check()) {
                answer = count;
                return;
            }
        }

        for (int i = x; i < h + 1; i++) {
            for (int j = 1; j < n; j++) {
                if (map[i][j] == 0 && map[i][j + 1] == 0) {
                    map[i][j] = 1;
                    map[i][j + 1] = 2;
                    dfs(i, count + 1);
                    map[i][j] = map[i][j + 1] = 0;
                }
            }
        }
    }

    private static boolean check() {
        for (int i = 1; i <= n; i++) {
            int x = 1, y = i;
            for (int j = 0; j < h; j++) {
                if (map[x][y] == 1) y++;
                else if (map[x][y] == 2) y--;
                x++;
            }
            if (y != i) return false;
        }
        return true;
    }
}