[BOJ] 15684 사다리 조작 - JAVA

1. 문제

15684번: 사다리 조작

* 이 문제는 꼭 문제 링크로 들어가서 힌트를 봐야한다!

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.

초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.

위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.

사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다. 이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다.

위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다. 아래 두 그림은 1번과 2번이 어떻게 이동했는지 나타내는 그림이다.

사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때, i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.

---

2. 풀이

메인

0.  입력을 boolean[][]에 저장했다. a번째 가로줄에 b,b+1 세로줄을 연결한 가로선이 있다면 true를 저장한다. 세로줄, 가로줄, 가로선이 헷갈리는데 가로줄은 가로로 놓인 줄이니까 height, 세로줄은 세로로 놓인 줄이니까 width다. 

1.  plus 함수를 호출하기 전에 첫번째 가지치기를 진행한다. 한 세로줄에 가로선이 홀수개 있다면 그 세로줄은 무조건 가로선이 하나 필요하다. 이렇게 가로줄이 더 필요한 세로줄이 3 보다 크다면 어차피 답을 구할 수 없으므로 -1을 출력하고 끝낸다.

2.  plus 함수 호출 뒤 MIN이 처음 초기화한 값 4와 다르다면 출력하고, 같다면 답을 찾지 못한 경우이므로 -1을 출력한다. 

static int N,M,H, MIN = 4;
static boolean[][] game;
public static void main(String[] args) throws Exception {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st = new StringTokenizer(in.readLine());
   N = Integer.parseInt(st.nextToken());//세로선
   M = Integer.parseInt(st.nextToken());//가로선
   H = Integer.parseInt(st.nextToken());//세로선마다 가로선을 놓을 수 있는 위치 개수

   game = new boolean[H+1][N+1];
   for(int i=0;i<M;i++){
      st = new StringTokenizer(in.readLine());
      game[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = true;
   }

   //첫번째 가지치기
   int cnt=0, tmp;
   for(int i=1;i<=N;i++){
      tmp = 0;
      for(int j=1;j<=H;j++){
         if(game[j][i]) tmp++;
      }
      if(tmp%2!=0) cnt++;
   }
   if(cnt>3){
      System.out.println(-1);
      return;
   }

   plus(0,1,1);
   if(MIN!=4) System.out.println(MIN);
   else System.out.println(-1);

}

 

사다리 체크

현재 사다리 상태를 체크한다. 

1번째 세로줄부터 N번째까지 돌면서 탐색한다. i는 가로줄 인덱스, j는 세로줄 인덱스다. [i][j]가 true라면 그 다음 세로줄과 연결되어있으므로 j++, [i][j-1]이 true라면 그 전 세로줄과 연결되어있으므로 j--한다.

모든 탐색이 끝난 뒤에도 start와 j가 동일해야한다. 그렇지 않다면 바로 false를 리턴한다.

private static boolean check(){
   int i,j;
   for(int start=1;start<=N;start++){
      i=1;j=start;
      for(;i<=H;i++){
         if(game[i][j]) j++;
         else if(game[i][j-1]) j--;
      }
      if(start!=j) return false;
   }
   return true;
}

 

사다리 더하기

1.  저장된 MIN이 현재의 cnt보다 같거나 작으면 종료한다.

2.  사다리 상태를 체크한다. true라면 바로 MIN에 cnt를 저장한다. 비교하지 않는 이유는 이미 1번에서 비교했기 때문이다.

3.  시작 h와 n을 받아서 그 위치부터 탐색한다. i는 입력받은 h부터 바로 돌면 되고, j은 h일때의 n위치부터 돌아야한다. 따라서 초기값 i=h, j=n으로 시작한다. 대신 i가 변경되어 h가 아니게 되면 j=1부터 시작한다. 

private static void plus(int cnt,int h,int n){
   if(MIN<=cnt){ //여기 가지치기 중요
      return;
   }

   if(check()) {
      MIN = cnt;
      return;
   }

   int i=h,j=n;//여기도 가지치기
   for(;i<=H;i++){
      if(i!=h) j=1;
      for(;j<N;j++){
         if(game[i][j] || game[i][j-1]) continue;
         game[i][j] = true;
         plus(cnt+1,i,j);
         game[i][j] = false;
      }
   }
}

---

3. 결과

가지치기를 안해서 시간초과가 많이 났다. 그리고 if(MIN<=cnt) return 이 부분도 중요하다. 이 부분 있고 없고에 따라서 2372ms->180ms만큼 차이가 난다.