[JS] 백준 15684번 : 사다리 조작

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

15684번: 사다리 조작

 

 

📋풀이방법

1.가로에 사다리가 없는 부분에 대하여 사다리를 추가해주었을 때 문제 조건을 맞는지 확인하면서 백트래킹을 돌아보면 된다. 

2.다만 백트래킹을 돌면서 확인해야할 조건은 가로선이 연속되면 안된다.

3.그리고 가로선을 하나씩 선택해주면서 갯수가 3개를 넘어간다면 return 조건을 추가해 3개이상 도는 경우를 가지치기 해준다.

 

 

1. 문제에서 주어진 사다리를 아래와 같이 변환시킨다.

2.  먼저 사다리를 진행시키는 부분을 작성한다.

 -사다리를 1번부터 5번 모두 순회한다.

 -h를 기준으로 아래로 내려가면서 현재 진행중인 위치와 그 이전 열에  1이 있다면 아래와 같이 값을 바꿔준다.

  -> 만약 현재 열에 1이 있다면 

   -> 이는 다음 번호로 이동해야한다는 뜻이므로 오른쪽으로 이동한다.

   -> 예를 들어 1번이 진행중인데 1번 열에 1이 있다면 2번으로 이동한다.

  -> 만약 이전 열에 1이 있다면 

   -> 이는 이전 번호로 이동해야한다는 뜻이므로 왼쪽으로 이동한다.

   ->예를 들어 2번이 진행중인데 1번에 1이 있다면 1번으로 이동한다.

3. 이 방식으로 start라는 변수를 만들어 1이 있다면 증가 혹은 감소시킨다.

4. 마지막에 start와 현재 진행중인 번호를 비교해서 같지않다면 답이 아니므로 중간에 종료시킨다,

 

 

1. 사다리를 1개 2개 3개 추가하는 DFS

2. 1개, 2개, 3개로 DFS를 실행한다.

3. DFS를 진행할때 설치할 사다리의 좌표 y,x와 cnt를 보내준다.

 -cnt는 현재 1개 설치하는 DFS인지 2개 설치하는 DFS인지 구분하기위한 변수다

 -DFS에 종료구문으로 사다리를 설치하고 cnt가 1인지 2인지 3인지에 따라 사다리를 진행시키면된다.

4. 이중 for문으로 돌면서 사다리가 설치가능한 부분을 찾는다.

 -이때 연속된 사다리를 피해준다.(사다리가 있거나 그 전에 있거나 그 이후에 있거나)

5. 설치가 가능한자리에 사다리를 1로 설치하고 DFS로 뻗어간다.

 -이때 설치한 좌표를 DFS로 넘겨줌으로써 만약 2개를 설치해야할 때 2번째 사다리 설치시 1번째 사다리가 설치되기 이전에 검사한 구역은 검사를 안해도된다.

 -즉 불필요한 부분을 검사하지않고 DFS로 보내준 1번째 사다리좌표 이후를 검사하고 설치한다.

6. 설치할때마다 cnt가 증가한다.

7.cnt가 1인지 2인지 3인지에 따라 DFS를 종료시키고 사다리를 진행시켜 시작과 끝이 같은번호가 되는지 확인한다.

 

 

 

📝내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let [n,m,h]=input.shift().split(" ").map(Number);
let W=[];
let target_cnt=0;
let ans=10000;
for(var i=0;i<m;i++){
    W.push(input.shift().split(" ").map(Number));
}

let arr=Array.from({length:40},()=>Array(40).fill(0));


// 사다리타기 체크 
function check() {
	for (var i = 1; i <= n; i++) {
		let start = i;// 1번 사다리부터 검사한다.
		for (var j = 1; j <= h; j++) {
			//만약 1번 열에 1이 있으면 다음 사다리로 이동하라는 뜻이다.
			//start를 증가시켜준다.
			if (start+1 <= n && arr[j][start] == 1) {
				start++;
			}
			//만약 1번 열을 기준으로 그 이전 번호의 사다리가 1번이면 이전 번호의 사다리로 이동하라는 뜻이다.
			//1번은 그 이전번호가 없다.
			//만약 2번인데 1번에 1이 있다면 2번에서 1번으로 이동해야하므로 start를 감소시킨다.

			else if (start-1 >=1 && arr[j][start-1] == 1) {
				start--;
			}
		}
		//한개의 열을 검사한후 start와 시작번호가 다르다면 정답이아니므로 중간에 종료시킨다.
		if (start != i) return false;
	}
	return true;
}

function DFS(h_cnt,n_cnt,cnt) {

	// 사다리 선택하는 횟수를 통해 가지치기 하기
	if (cnt == target_cnt) { //사다리가 1개 추가될때 2개 추가될 때.. 체크함
		if (check()) {
			ans = cnt;
		}
		
		return;
	}

	//매개변수 설정을 잘 해주면 이전에 돌았던 거 다시 안돌아도 되서
	//가지치기를 할 수 있다. 
	//h_cnt와 n_cnt를 통해서 이전에 사다리를 설치하거나 설치가 안디는 부분은 생략할 수 있다.
	for (var i = h_cnt; i <= h; i++, n_cnt = 1) {
		for (var j = n_cnt; j < n; j++) {
        	//연속된 사다리 선택 피해주기
			if (arr[i][j - 1] || arr[i][j] || arr[i][j + 1]) continue;
			else {
				arr[i][j] = 1;
				//사다리를 설치하고 그 설치한 좌표를 넘겨줌으로써 이후 사다리 설치시 불필요한 검사를 하지않는다.]
				//즉 1번째 사다리를 설치하면 그 이전에 있던 좌표들은 설치할 수 없다는 뜻이다. 
				DFS(i, j, cnt + 1);
				arr[i][j] = 0;
			}
		}
	}

}


W.forEach((tt)=>{
    let [a,b]=tt;
    arr[a][b]= 1;
})

//1개 2개 3개의 사다리를 설치했을 때를 위해 3번의 반복문을 실행한다.
//문제에 0개일때도있으므로 0일 때도 진행한다.
for(var i=0;i<=3;i++){
    target_cnt=i;
    DFS(1,1,0);
    if(ans !=10000){
        console.log(ans);
        return;
    }

}
console.log(-1);

 

💢어려웠던 점

1. 무작정 완전탐색으로 모든 경우의 수를 구하려고 했다.

 -1개 설치했을 때 2개 설치했을 때는 그냥 위처럼 1,2,3이라는 종료조건을 주고 이중for문을 재귀로 돌리면 됐었다.

 -이 조건에서 생각을 오래했다.

2. 주어진 문제의 사다리를 만들 때 위 처럼 간단하게 열마다 1을 체크해주는 방법이 아닌 복잡하게 공간을 늘려 사다리배열을 만들어서 더 복잡하게 되었다.

-이런식으로 배열을 넓혀서 진행했지만 나중에 늘려버림으로써 더 복잡하게 구현해야했다.