[boj]: 사다리 조작 LINK

문제

h개의 가로줄과 n개의 세로선을 갖고 있는 사다리가 사다리타기를 통하여 각 세로선이 사다리를 타고 끝까지 내려갈때 세로선이 처음 위치한 곳과 같은 번호로 내려와야 한다.
(m개의 가로선은 원래 있던 선이다.)

요약설명

원래 있던 사다리는 제거하지 않고 원래 있던 사다리 가로선에서 1,2,3개의 가로선을 놓고 세로 선이 위치한 곳에서 출발하여 같은 위치로 내려올 수 있는지를 구현하는 문제이다.

풀이

• 조합으로 가로선을 하나씩 놓으면서 내려올 때까지 처음 위치 인지 체크를 해야한다.

  • 해당 칸에 가로선을 놓거나 안놓거나 경우의 수는 2가지이다.

• 해당 가로선을 놓게 되면 다음 인덱스 까지 영향을 미치므로 다다음으로 넘어가야 한다.

• 격자 배열안에 오른쪽 다리가 있으면 +1, 왼쪽 다리가 있으면 -1로 표시했다.

• 만약 4개 이상 이면 -1을 출력한다.

입력예제

2 0 3

[3][2] 격자 배열 안에
0 0
0 0
0 0

1 -1
1 -1
1 -1

3가지 다리를 놓았다.

0,0의 1을 밟고 대각석 방향인 1,1로 그 -1을 밟고 다음 2,1로 그러면 해당 칸 0컬럼에 출발하여 0 컬럼으로 오게된다.
하지만 3가지를 뽑지 않아도 되므로
0 0
0 0
0 0
그대로 내려가면 사다리를 하나도 안놓아도 된다.

답 : 0

Code

package AL_CS_STUDY.Weekly17;

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

public class LadderManipulation {

    static int n, m, h;
    static int ladder[][];
    static int min=4;
    public static void main(String[] args) throws IOException {
        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());
        ladder=new int[h][n];
        for (int i = 0; i < m; i++) {
            st=new StringTokenizer(br.readLine());
            int a=Integer.parseInt(st.nextToken());
            int b=Integer.parseInt(st.nextToken());
            ladder[a-1][b-1]=1;
            ladder[a-1][b]=-1;
        }
        pick(0,0);
        if(min>=4)
            System.out.println(-1);
        else
            System.out.println(min);


    }
    static void pick(int cnt,int idx)
    {
        if(cnt==3 || idx>= h*n)
        {
            if(check())
            {
                min=Math.min(min,cnt);
            }
            return;
        }
       int i=idx/n;
       int j=idx%n;
       if(j!=n-1 && ladder[i][j]==0 && ladder[i][j+1]==0)
       {
           ladder[i][j]=1;
           ladder[i][j+1]=-1;
           pick(cnt+1,idx+2);
           ladder[i][j]=ladder[i][j+1]=0;
       }
       pick(cnt,idx+1);
    }
    static boolean check()
    {
        for (int i = 0; i < n; i++) {
            int col=i;
            int row=0;
            while (row <h)
            {
                if(ladder[row][col]==-1)
                {
                    col--;
                }
                else if(ladder[row][col]==1)
                {
                    col++;
                }
                    row++;
            }
            if(col!=i)
                return false;
        }
        return true;
    }
}