백준15684 : 사다리 조작

백준15684 : 사다리 조작

문제

N개의 세로선과 H개의 가로선이 있을 때 i번째 세로선을 타고 다시 i번째로 끝나기 위해 추가해야 될 가로선의 개수를 구하는 문제

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

접근방법

• 3번까지만 사다리를 놓는다는 것을 보고 1번, 2번, 3번 사다리를 일일이 놓아본 다음 다시 본인의 세로선에서 끝나는지를 확인하도록 하였다.

• 기본로직

  // i-i 연결 여부 확인
  if(search(map) == false){ // 초기상태 확인
      ++result;
      isTrue = combi_1(); // 가로선 1개 추가 후 확인
      if(isTrue == false){ 
          ++result;
          isTrue = combi_2(); // 가로선 2개 추가 후 확인
          if(isTrue == false){
              ++result;
              isTrue = combi_3(); // 가로선 3개 추가 후 확인
              if(isTrue == false)
                  result = -1;
          }
      }
  }
  System.out.println(result);

1. i번째 세로선이 사다리를 타고 도달하는 세로선 확인하는 함수 search()

   • 먼저 입력을 받을 때 가로는 N-1개, 세로는 H개의 배열로 받아지는 것을 알 수 있다. 즉, map[i][j] 는 i번째 가로선과 j와 j+1번째 세로선을 잇는 선이 된다.

   • map[H][N-1] 배열에서 i번째 세로선에서 시작해 사다리를 타고 이동할 곳을 알기 위해서는 map[i][j-1] 과 map[i][j] 을 확인해야 한다. 즉, 첫번째경우가 true라면 왼쪽으로 이동하는 것이고, 두번재 경우가 true라면 오른쪽으로 이동하는 경우이다.

   • 여기서 첫번째 세로선과 마지막 세로선은 한방향으로만 이동할 수 있기 때문에 예외처리를 해주어야 한다.

   • map[i][j-1], map[i][j] 에 따라서 세로선 인덱스가 바뀌기 때문에, 마지막에 처음 시작한 인덱스와 비교해주기 위해 n_tmp 를 사용하였다.

   • 소스코드는 아래와 같다.

     // i-i 연결여부 확인
     static boolean search(boolean[][] map){
     ​
         boolean result = true;
         for(int n=1; n<=N; n++){
             int n_tmp = n;
             for(int h=1; h<=H; h++) {
                 // 왼쪽으로 이동 (1은 확인x)
                 if (n > 1 && map[h][n - 1] == true) {
                     --n;
                 }// 오른쪽으로 이동 (N은 확인x)
                 else if (n < N && map[h][n] == true){
                     ++n;
                 }
             }
             if(n != n_tmp){
                 result = false;
                 break;
             }
             n = n_tmp;
         }
     ​
         return result;
     }

2. 가로선을 하나 추가하는 경우는 이차원 배열을 훑으면서 하나씩 가로선을 더해주면 된다.

   • 소스코드

     static void combi_1(){
        boolean map_tmp[][] = new boolean[H+1][N];
         for(int i=1; i<=H; i++)
             for(int j=1; j<=N-1; j++)
                 map_tmp[i][j] = map[i][j];
     ​
         for(int i=0; i<pos_set.length; i++){
             if(pos_set[i] != null){
                 map_tmp[pos_set[i].x][pos_set[i].y] = true;
                 if(search(map_tmp)){
                     isTrue = true;
                     break;
                 }// 바뀐 맵 원래대로 돌려놓기
                 map_tmp[pos_set[i].x][pos_set[i].y] = false;
             }
         }
     }

3. 가로선을 2개, 3개 추가하는 경우는 combination함수를 사용하였다.

• (x, y)의 위치를 조합으로 꺼내야하기 때문에, Pos 객체를 이용해 가로선이 없는 위치를 배열에 넣어주었다.

소스코드

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
​
public class Main{
​
    static int N;
    static int M;
    static int H;
    static boolean isTrue;
    static boolean map[][];
    static Pos[] pos_set = new Pos[H*(N-1)];
​
​
    static class Pos{
        int x; int y;
        public Pos(int x, int y) {this.x = x; this.y = y;}
    }
​
    // i-i 연결여부 확인
    static boolean search(boolean[][] map){
​
        boolean result = true;
        for(int n=1; n<=N; n++){
            int n_tmp = n;
            for(int h=1; h<=H; h++) {
                // 왼쪽으로 이동 (1은 확인x)
                if (n > 1 && map[h][n - 1] == true) {
                    --n;
                }// 오른쪽으로 이동 (N은 확인x)
                else if (n < N && map[h][n] == true){
                    ++n;
                }
            }
            if(n != n_tmp){
                result = false;
                break;
            }
            n = n_tmp;
        }
​
        return result;
    }
​
    static void combi_1(){
       boolean map_tmp[][] = new boolean[H+1][N];
        for(int i=1; i<=H; i++)
            for(int j=1; j<=N-1; j++)
                map_tmp[i][j] = map[i][j];
​
        for(int i=0; i<pos_set.length; i++){
            if(pos_set[i] != null){
                map_tmp[pos_set[i].x][pos_set[i].y] = true;
                if(search(map_tmp)){
                    isTrue = true;
                    break;
                }// 바뀐 맵 원래대로 돌려놓기
                map_tmp[pos_set[i].x][pos_set[i].y] = false;
            }
        }
    }
​
    static void combi_2(int arr[]){
        boolean map_tmp[][] = new boolean[H+1][N];
        for(int i=1; i<=H; i++)
            for(int j=1; j<=N-1; j++)
                map_tmp[i][j] = map[i][j];
​
        map_tmp[pos_set[arr[0]].x][pos_set[arr[0]].y] = true;
        map_tmp[pos_set[arr[1]].x][pos_set[arr[1]].y] = true;
​
        if(search(map_tmp))
            isTrue = true;
    }
​
    static void combi_3(int arr[]){
        boolean map_tmp[][] = new boolean[H+1][N];
        for(int i=1; i<=H; i++)
            for(int j=1; j<=N-1; j++)
                map_tmp[i][j] = map[i][j];
​
        map_tmp[pos_set[arr[0]].x][pos_set[arr[0]].y] = true;
        map_tmp[pos_set[arr[1]].x][pos_set[arr[1]].y] = true;
        map_tmp[pos_set[arr[2]].x][pos_set[arr[2]].y] = true;
​
        if(search(map_tmp))
            isTrue = true;
    }
​
    static void combination(int arr[], int index, int n, int r, int target){
        if(arr.length == 1) {
            combi_1();
        }else {
            if (r == 0) {
                if (arr.length == 2) { // 두 개 고르는 경우
                    combi_2(arr);
                } else if (arr.length == 3) { // 세 개 고르는 경우
                    combi_3(arr);
                }
            } else if (target == n) {
                return;
            } else {
                arr[index] = target;
                combination(arr, index + 1, n, r - 1, target + 1);
                combination(arr, index, n, r, target + 1);
            }
        }
    }
​
​
    public static void main(String[] args) throws IOException {
​
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
​
        String input[] = in.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        H = Integer.parseInt(input[2]);
        map= new boolean[H+1][N]; // 한 칸씩 크게 맵을 만들어 줌(H x N-1)
​
        for(int i=0; i<M; i++){
            String line[] = in.readLine().split(" ");
            map[Integer.parseInt(line[0])][Integer.parseInt(line[1])] = true;
        }
​
        isTrue = false;
        int result = 0;
​
        //pos_set = new Pos[H*(N-1)];
        ArrayList<Pos> pos_list = new ArrayList();
        int p_index = 0;
        for(int i=1; i<=H; i++)
            for(int j=1; j<=N-1; j++)
               if(map[i][j] == false)
                   pos_list.add(new Pos(i, j));
        pos_set = pos_list.toArray(new Pos[p_index]);
​
        // i-i 연결 여부 확인
        if(search(map) == false){ // 초기상태 확인
            ++result;
            int arr_1[] = new int[1];
            combination(arr_1,0, pos_set.length, 1, 0);
            if(isTrue == false){ // 가로선 1개 추가 후 확인
                ++result;
                int arr_2[] = new int[2]; // 가로선 2개 추가 후 확인
                combination(arr_2,0, pos_set.length, 2, 0);
                if(isTrue == false){
                    ++result;
                    int arr_3[] = new int[3];
                    combination(arr_3,0, pos_set.length, 3, 0);
                    if(isTrue == false)
                        result = -1;
                }
            }
        }
​
        System.out.println(result);
​
    }
}

- 정답은 맞았지만 시간 상 수정이 필요하다.