[삼성SW테스트] 사다리 조작 15684(백준)

삼성 SW테스트

#15684 - 사다리 조작(Ladder Manipulation)

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

사용한 개념

1. 중복이 없는 조합

해당 문제를 푸는데 있어 많은 개념이 사용되지는 않았습니다. 다만.. 아래와 같은 고민을 많이했습니다.

1. 사다리를 어떻게 저장하고 표현할 것인가??

2. 사다리를 탈때, 원리가 무엇이고 해당 원리를 어떻게 반영할까?...

또한, 문제를 풀면서...보완해야할 점도 생각하게 되었습니다. 중복이 없는 조합을 재귀로 구현했지만, 나중에는 재귀방식이 아닌 더 간단한 방식으로 조합을 구하는 방법을 강구해야 할 것 같습니다. 소스가 복잡해지고, 예외처리를 해야하는 부분이 늘어나는 느낌이라서요...ㅎㅎ

자 그럼 ...

1. 사다리를 어떻게 저장하고 표현할 것인가??

-> 저는 2차원배열을 이용해서 가로 세로가 교차되는 것을 그대로 저장할 수 있도록 생각해봤습니다. 여기서 꼭지점은 가로선을 연결시킬 수 있는 포인트가 됩니다.

2. 사다리를 탈때, 원리가 무엇이고 해당 원리를 어떻게 반영할까?...

-> 여기서 특징은 미리 그어진 가로선을 제외하고 사용자가 설치할 수 있는 가로선을 추출할 때

맨 끝 점이 몰려있는 마지막 세로선 즉 2차원 배열에서 마지막 열은 제외해야 한다는 것입니다.

왜냐면 저는 가로선을 무조건 왼쪽에서 오른쪽으로 그을거라서요... 맨 마지막 열에 점을 선택해도.. 더이상 진행할 오른쪽 점이 없기 때문에 제외시키는 것이지요..

-> 또한, 하나의 가로선이 있다고 해도 왼쪽으로 오느냐 오른쪽으로 오느냐에 따라 진행방향이 달라지는 원리가 있습니다. 따라서 진행될 방향을 결정하기 위해 왼쪽 점은 1번 오른쪽 점은 2번으로 저장하여 사다리 진행방향을 반영하여 2차원 배열에 저장했습니다.

package SamsungTest;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class LadderManipulation {

	static ArrayList<Point> installable = 	new ArrayList<>();
	static int[][] orignalLadder;
	public static void main(String[] args) {
		//1. point자료형으로 가로(시작점,끝점)을 그린다.
		//2. 사용자가 임의로 그릴 수 있는 가로 공간을 따로 분별한다.
		//3. 조합을 적용하여 nCr (r=0,r=1,r=2,r=3)인 경우를 구한다.(r>3 부터 -1)
		
		Scanner sc = new Scanner(System.in);
	
		int h = sc.nextInt();
		int r = sc.nextInt();
		int w = sc.nextInt();
		
		orignalLadder = new int[w][h];
	
		for(int i=0; i<r; i++){
			int y = sc.nextInt();
			int x = sc.nextInt();
			orignalLadder[y-1][x-1] = 1;
			orignalLadder[y-1][x] = 2;
		}
	
		/*System.out.println("origin");
		for(int i=0; i<orignalLadder.length; i++){
			for(int j=0; j<orignalLadder[0].length; j++){
				System.out.print(orignalLadder[i][j]+" ");
			}
			System.out.println();
		}*/
		//2. 사용자가 그릴 수 있는 사다리 공간을 저장한다.
		for(int i=0; i<orignalLadder.length; i++){
			for(int j=0; j<orignalLadder[0].length; j++){
				//끝점은 필요없음.무조건 -> 해당방향으로 설치할거임
				if(orignalLadder[i][j] == 0 && j !=orignalLadder[0].length-1){
					installable.add(new Point(i, j));
				}	
			}
		}
		
		int n = installable.size();
		int[] arr = new int[n];
		int[] combArr = new int[n];
		for(int i=0; i<n; i++) arr[i] = i;
		
		for(int i=0; i<=r; i++){
			doCombination(combArr, n, i, 0, 0, arr);
		}
		
		//불가능
		System.out.println(-1);

	}

	private static void doCombination(int[] combArr, int n, int r, int index, int target, int[] arr) { 
    	// r ==0 이란 것은 뽑을 원소를 다 뽑았다는 뜻.
    	if(r == 0){
    		int[][] copyArray = new int[orignalLadder.length][orignalLadder[0].length];
    		arrayCopy(orignalLadder, copyArray);
    		
            for(int i=0; i<index; i++){
            	//3보다 크면..-1로 종료
            	if(index > 3) {
            		System.out.println(-1);
            		System.exit(0);
            	}
            	int x = installable.get(arr[combArr[i]]).x; //i
        		int y = installable.get(arr[combArr[i]]).y; //j
        		
        	// -> 이 방향으로만 설치 따라서, 오른쪽 유무 확인
        		if(copyArray[x][y]==0 && copyArray[x][y+1]==0){
        			copyArray[x][y] = 1;
	        		copyArray[x][y+1] = 2;
	        	}else{
	        		return;
	        	}
            
            }

            //한개의 조합에 대해 사다리 설치 완료
            boolean flag = followLadder(copyArray);
            if(flag){
            	System.out.println(index);
            	 System.exit(0);
            }
			
        }else if(target == n){ 
        	return;
        }else{
            combArr[index] = target;
            doCombination(combArr, n, r-1, index+1, target+1, arr);
            doCombination(combArr, n, r, index, target+1, arr); 
        }
		
	}

	
	private static boolean followLadder(int[][] copyArray) {
		  for(int i=0; i<copyArray[0].length; i++){
	        	int indexX = 0;
	        	int indexY = i;
	        	boolean flag = true;
	        	while(flag){
	        		
	        		//System.out.println("P : "+indexX+" "+indexY);
	        		if(indexX == copyArray.length) break;    	
	        		int v = copyArray[indexX][indexY];
	        		indexX++;
	        		switch (v) {
					case 1:
						indexY++;	
						break;
					case 2:
						indexY--;
						break;
					}
	        	}
	        	
	        	if(i != indexY){
	        		return false;
	        	}        	
	        	
	        }
		  return true;
		
	}

	private static void arrayCopy(int[][] array, int[][] copyarray){
		for(int i=0; i<array.length; i++){
			copyarray[i] = array[i].clone();
		}
	}
	
	

}