사다리조작(백준_15684)

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

15684번: 사다리 조작

문제 설명

결론은 가로선을 추가해 세로선의 결과가 자신의 번호가 나오게 해야 한다는 것이다.

그때 추가한 가로선의 개수를 출력하는 문제이다. 단 추가할 수 있는 가로선은 최대 3개이다.

 

문제에 대한 아이디어 및 구

이렇게 어떤 것을 추가하고 빼는 문제들은 브루트 포스를 사용해서 모든 경우를 검사해 보는 경우가 많다. 그래서 나도 이 문제를 풀 때 2차원 배열로 사다리를 만들고 하나씩 추가해 가면서 모든 경우를 검사하려고 했다.

위의 예제를 사다리로 그려보면 이렇게 된다.

총 3개의 가로선을 추가해야 1번은 1, 2번은 2 이런 형식으로 나온다.

 

사다리를 2차원 배열로 나타내기

사다리를 표현 하는 것부터 문제였다. 일단 2차원 배열로 표현을 하고 이어진 부분에는 숫자르 넣어서 표현하기로 했다.

생각해 보면 왼쪽에서 접근하는 가로선은 오른쪽으로만 오른쪽에서 접근하는 가로선은 왼쪽으로만 갈 수 있다. 이것을 사용해서 사다리를 표현해 보았다.

 

왼쪽에서 접근하는 가로선은 1로 표현하고 오른쪽에서 접근하는 가로선은 2로 표현했다. 이렇게 하면 1번을 만나면 무조건 오른쪽으로 2번을 만나면 무조건 왼쪽으로 가도록 표현했다.

• 사다리를 2차원 배열로 나타내는 코드 

arr = new int[m+1][n+1]; // 사다리를 나타내는 배열
for(int i =0; i<h; ++i) { // 가로선의 갯수 만큼 for문
    st = new StringTokenizer(bf.readLine());
    int u = Integer.parseInt(st.nextToken());
    int v = Integer.parseInt(st.nextToken());
    arr[u][v] = 1;
    arr[u][v + 1] = 2;
}

 

조건에 맞게 출력되는지 검사하는 부분

• 1을 만나면 오른쪽 2를 만나면 왼쪽으로 간다.
• 2차원 배열의 마지막 가로선에 도착하면 지금 위치한 세로선이 출발한 세로선과 동일한지 체크한다.

public static boolean check() {
    for (int i = 1; i <= n; ++i) {
        int ny = 1;
        int nx = i;
        while (ny <= m) {
            if (arr[ny][nx] == 1) ++nx; //오른쪽으로 이동
            else if (arr[ny][nx] == 2) --nx; //왼쪽으로 이동
            ++ny; //오른쪽이나 왼쪽으로 이동 후 아래로 한칸 내림
        }
        if (nx != i) return false; // 현재 세로선과 출발한 세로선이 일치하는지 검사
    }
    return true;
}

 

백트래킹을 이용해 가로선을 추가해가면서 체크하기

• 가로선을 추가할 수 있는 개수를 0에서 3까지 올리면서 검사한다.
• (1,1) 부터 가로선을 추가하면서 위에 check 검사를 시작한다.

for(int i =0; i<= 3; ++i ){
    result = i;
    plus(0);
    if(finish) break;
}

public static void plus(int count){
    if(finish) return;
    if(result == count) {
        if(check()) finish = true;
        else finish = false;
        return;
    }
    for(int i = 1; i<=m; ++i){
        for(int j=1; j< n; ++j){
            if(arr[i][j] == 0 && arr[i][j+1] == 0){ // 연속으로 가로선이 존재할 수 없으므로 체크한다.
                arr[i][j] = 1;
                arr[i][j+1] =2;
                plus(count+1);
                
                //백트래킹 부분
                arr[i][j] = 0;
                arr[i][j+1] = 0;
            }
        }
    }
}

 

전체 코드

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

public class Main {
    static int arr[][];
    static int result=0;
    static int n,h,m;
    static boolean finish = false;
    public static void main(String []args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[m+1][n+1];
        for(int i =0; i<h; ++i) {
            st = new StringTokenizer(bf.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            arr[u][v] = 1;
            arr[u][v + 1] = 2;
        }
        for(int i =0; i<= 3; ++i ){
            result = i;
            plus(0);
            if(finish) break;
        }
        if(finish) System.out.println(result);
        else System.out.println(-1);
    }
    public static void plus(int count){
        if(finish) return;
        if(result == count) {
            if(check()) finish = true;
            else finish = false;
            return;
        }
        for(int i = 1; i<=m; ++i){
            for(int j=1; j< n; ++j){
                if(arr[i][j] == 0 && arr[i][j+1] == 0){
                    arr[i][j] = 1;
                    arr[i][j+1] =2;
                    plus(count+1);
                    arr[i][j] = 0;
                    arr[i][j+1] = 0;
                }
            }
        }
    }
    public static boolean check() {
        for (int i = 1; i <= n; ++i) {
            int ny = 1;
            int nx = i;
            while (ny <= m) {
                if (arr[ny][nx] == 1) ++nx;
                else if (arr[ny][nx] == 2) --nx;
                ++ny;
            }
            if (nx != i) return false;
        }
        return true;
    }
}

 

 

https://github.com/Heron-Woong/CodingTest_Practice/commit/28bc3e37e715fc9c9da8c241adffe2011690726c

백준_15684, 사다리 조작 · Heron-Woong/CodingTest_Practice@28bc3e3