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

[ 문제 ]

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

 

간단하게 설명하면 일반적인 사다리게임에서 추가적으로 최대 3개의 선을 추가하여 모든 i번 세로선들의 결과가 i로 나오게 만드는 최소 가로선 추가 개수를 출력하는 문제이다.

 

[ 구현 ]

 

적용시킨 알고리즘은 백트래킹(Backtracking) 기반 DFS로 조합을 탐색하는 완전탐색(Brute Force)

 

우선 주어진 가로선들의 입력을 받았을 때

map[a][b] = 1; // 오
map[a][b + 1] = -1; // 왼

와 같은 방식으로 사다리를 구현해주었다.

 

map[a][b] = 1만 해두고, 조건 검사시에 map[a][b - 1] ==1 인지 함께 검사해주는 방식으로 구현해도 무방할 듯 하였지만, 뭔가 이 방식이 더 깔끔해보여서 고민끝에 이렇게 구현했다.

 

--------------

 

private static void dfs(int r, int c, int cnt) {
    if (check()) {
        ans = Math.min(ans, cnt);
        return;
    }

    else if (cnt == 3) {
        return;
    }

    for (int i = r; i <= h; i++) {
        int start = (i == r ? c : 1); // 이전 위치와 다른 행이면 열 위치 1부터 탐색
        for (int j = start; j <= n - 1; j++) {
            if (isAvailableLine(i, j)) {
                map[i][j] = 1;
                map[i][j + 1] = -1;
                // 같은 행이면 j+2부터(인접 불가), 다음 행으로 넘어가면 1부터
                dfs(i, j + 2, cnt + 1);
                map[i][j] = 0;
                map[i][j + 1] = 0;
            }
        }
    }
}

 

그리고 dfs를 통해 가능한 가로선들을 조합, 이후 현재 상태에서 모든 세로선들이 자신의 위치로 내려올 수 있는지 판단해주었다.

보통의 backtracking 문제들은 cnt == 3와 같은 종료 조건 도달시점에 최적의 해를 갱신하는데,

이 문제의 경우 더 적은 가로선을 가지고도 충분히 최종 조건을 만족할 수 있으므로 그 부분까지 신경써서 해를 갱신해주었다.

 

가로선을 조합할 때, 이전에 뽑은 위치와 인접한 경우는 불가능하므로 j + 2를 통해 해당 위치를 건너뛰었고,

만일 해당 열의 끝에 도달해 다음 행을 고려해야하는 경우 다시 1열부터 후보군을 선정해야하기 때문에 해당 부분을

start = (i == r ? c : 1)와 같은 형식으로 처리해주었다.

 

private static boolean isAvailableLine(int r, int c) {
    if (map[r][c + 1] == 1) return false;
    else if (map[r][c] == 1) return false;
    else if (map[r][c - 1] == 1) return false;
    return true;
}

가능한 가로선인지 판별하는 로직은

1. 현재 위치에 가로선이 있는지

2. 현재 위치에서 열 + 1의 위치에 가로선이 있는지

3. 현재 위치에서 열 - 1의 위치에 가로선이 있는지

를 판단해주었고, 이때 map[a][0]의 위치는 어차피 값이 0으로 초기화되어있고 갱신되지 않으므로 고려해주지 않아도 되었다.

 

 

가로선을 뽑아놓고 모든 세로선들이 최종적으로 자기 위치에 도착하는지를 확인하는 로직은 직관적이므로 생략하겠다.

[ 코드 ]

package p_15684;

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

public class Main {

    static int n, m, h;
    static int[][] map;
    static int ans = 4;

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        void close() {
            try {
                br.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    private static void readInput() {
        Reader reader = new Reader();
        n = reader.nextInt();
        m = reader.nextInt();
        h = reader.nextInt();

        map = new int[h + 1][n + 1];

        for (int i = 0; i < m; i++) {
            int a = reader.nextInt();
            int b = reader.nextInt();

            map[a][b] = 1; // 오
            map[a][b + 1] = -1; // 왼
        }
    }

    private static void dfs(int r, int c, int cnt) {
        if (check()) {
            ans = Math.min(ans, cnt);
            return;
        }

        else if (cnt == 3) {
            return;
        }

        for (int i = r; i <= h; i++) {
            int start = (i == r ? c : 1); // 이전 위치와 다른 행이면 열 위치 1부터 탐색
            for (int j = start; j <= n - 1; j++) {
                if (isAvailableLine(i, j)) {
                    map[i][j] = 1;
                    map[i][j + 1] = -1;
                    // 같은 행이면 j+2부터(인접 불가), 다음 행으로 넘어가면 1부터
                    dfs(i, j + 2, cnt + 1);
                    map[i][j] = 0;
                    map[i][j + 1] = 0;
                }
            }
        }
    }

    private static boolean isAvailableLine(int r, int c) {
        if (map[r][c + 1] == 1) return false;
        else if (map[r][c] == 1) return false;
        else if (map[r][c - 1] == 1) return false;
        return true;
    }

    private static boolean check() {
        for (int i = 1; i <= n; i++) {
            if (!checkLine(i)) return false;
        }
        return true;
    }

    private static boolean checkLine(int idx) {
        int pos = idx;
        for (int i = 1; i <= h; i++) {
            if (map[i][pos] == 1) pos++;
            else if (map[i][pos] == -1) pos--;
        }
        if (pos == idx) return true;
        else return false;
    }

    private static void printAnswer() {
        if (ans == 4) System.out.println(-1);
        else System.out.println(ans);
    }

    private static void solution() {
        readInput();
        dfs(1, 1, 0);
        printAnswer();
    }

    public static void main(String[] args) {
        Main.solution();
    }
}

 

 

[ 마무리 및 느낀 점 ]

 

요즘은 삼성 SW 역량 기출 문제들을 풀어보고 있다.

솔직히 문제 하나하나 구현이 복잡하긴 하지만, 좋은 문제들이라는 느낌을 받았다.

안 풀어본 문제들을 전부 풀어봐야겠다.