🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[N], ...inputs] = fs
.readFileSync(path)
.toString()
.trim()
.split('\n')
.map((it) => it.split(' ').map(Number));
const map = Array.from({ length: 2 * N }, () => Array());
const visited = Array(2 * N).fill(false);
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
if (inputs[i][j]) map[i + j].push([i, j]);
}
}
let ans = 0;
const bt = (n, cnt) => {
if (ans >= cnt + 2 * N - 1 - n) return;
if (n === 2 * N - 1) {
ans = Math.max(ans, cnt);
return;
}
for (const [ci, cj] of map[n]) {
if (!visited[ci - cj]) {
visited[ci - cj] = true;
bt(n + 1, cnt + 1);
visited[ci - cj] = false;
}
}
bt(n + 1, cnt);
};
bt(0, 0);
console.log(ans);
🟢 풀이
⏰ 소요한 시간 : -
정신나갈뻔 한 시간초과들...
이 문제는 백트래킹의 대표 문제인 N-Queen과 같은 아이디어로 부터 풀이가 시작된다.
N-Queen은 X축, Y축, 대각선 이렇게 따져줬다면, 비숍은 하나의 대각선당 하나만 체크하면 된다.
대각선은 기울기가 양수인 방향이 있고, 음수인 방향이 있는데 기울기가 양수인 대각선을 기준으로만 백트래킹을 수행한다. 모든 경우의 수를 다 도는 것은 시간초과가 발생하기 때문이다...!
따라서 양수인 대각선을 기준으로 map을 만들어 줄텐데, i+j를 기준으로 배열을 만들어준다.
즉 map[i+j]는 아래처럼 i와 j를 더해서 될 수 있는 모든 값을 모아 넣는다.
map[0]=[[0, 0]]map[1]=[[1, 0], [0, 1]]map[2]=[[2, 0], [1, 1], [0, 2]]
그럼 총 0부터 2n-1까지 반복하면서 map[n]을 순회하며 이 경우의 수만 백트래킹을 수행하면 된다.
이 map 배열은 기울기가 양수인 방향만 체크했기 때문에 기울기가 음수인 방향은 visited 배열로 체크해주면 된다.
사실 여기까지 하면 시간초과가 발생한다. 따라서 '가지치기'를 사용해 시간초과를 유발할 수 있는 요소를 최대한 없애준다.
1. 첫 가지치기는 탐색을 하다가 남은 모든 요소에서 최대값으로 선택해도 ans값보다 작을 경우는 더 이상 탐색을 하지 않는다.
2. 흰 색 위치에 있는 말은 흰 색 위치로 밖에 이동하지 못한다. 마찬가지로 검은색 위치에 있는 말은 검은색 위치로 밖에 이동 못한다는 점을 적용한다.
근데 난 1번만 적용했다. 2번은...나중에..~
설명이 매우 난잡한데... 아래에 첨부한 유튜브에서 잘 설명해주시니까 유튜브를 참고하시길...
🔵 Ref
