🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const girls = fs
.readFileSync(path)
.toString()
.trim()
.split('\r\n')
.map((it) => it.split(''));
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
let answer = 0;
const checkBfs = (selected) => {
const map = Array.from({ length: 5 }, () => Array(5).fill(false));
const q = [selected[0]];
map[selected[0][0]][selected[0][1]] = true;
while (q.length) {
const [x, y] = q.shift();
for (let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < 5 && (ny < 5) & !map[nx][ny]) {
if (selected.some((pos) => pos[0] === nx && pos[1] === ny)) {
map[nx][ny] = true;
q.push([nx, ny]);
}
}
}
}
return selected.every((pos) => map[pos[0]][pos[1]]);
};
const bt = (selected, sCnt, yCnt, start) => {
if (selected.length === 7) {
if (checkBfs(selected)) answer++;
return;
}
for (let i = start; i < 25; i++) {
const x = Math.floor(i / 5);
const y = i % 5;
const girl = girls[x][y];
if (girl === 'S') {
bt([...selected, [x, y]], sCnt + 1, yCnt, i + 1);
} else if (girl === 'Y' && yCnt <= 2) {
bt([...selected, [x, y]], sCnt, yCnt + 1, i + 1);
}
}
return false;
};
bt([], 0, 0, 0);
console.log(answer);
🟢 풀이
⏰ 소요한 시간 : 답지보고 2시간
나에게 너무 어려운 문제였다. 문제를 보고 백트래킹으로 구현했는데 단순 백트래킹으로만 구현하게 되면 문제에서 주어진 첫 테스트 케이스의 두번째 경우의수를 탐색하지 못한다.
결국 지피티의 도움을 받았는데 풀이를 요약해보자면 다음과 같다.
1. 백트래킹을 사용해서 7명을 뽑는 모든 조합을 구해준다.
2. bfs로 구해진 조합이 서로 연결되어 있는 조합인지 확인한다.
1번의 백트래킹을 사용해서 7명을 뽑는 모든 조합을 구해주는 bt 코드부터 확인해보자.
뽑힌 인원이 7명이라면 조합을 체크하고 answer를 증가시킨다. 7명을 다 뽑지 못했다면 for문을 돌면서 사람을 뽑게 되는데 이때 중복을 피하기 위해 start 부터 뽑아준다. 7명의 학생을 뽑을 때 순서는 중요하지 않다. 1 2 3 을 뽑든, 3 1 2 를 뽑든 같은 경우로 처리되기 때문에 우리는 이미 내가 뽑은 수보다 더 작은수를 뽑을 필요가 없다. 따라서 시작은 start 부터 뽑아준다. 나중에 bfs로 확인할 때 사용할 x좌표와 y좌표를 구해서 보내준다. 그리고 백트래킹을 재귀호출하기전에 도연이가 4명이 뽑혀 이다솜파를 만들지 못하게 되는 경우를 체크해준다. 이렇게 돌다보면 가능한 조합의 수가 무려 오천여개가 나오는에 이 오천여개에 대해 bfs를 수행해준다.
구현하면서 메모리 초과 나지않을까 ? 걱정했는데 안나나보다 ㄷㄷ 25칸밖에 없어서 그런듯
매번 맵을 새로 만들어 주고 아까 만든 조합의 첫 번째 요소를 큐에 집어 넣는다. 그 후 일반적인 bfs 로직과 동일하게 큐가 빌때까지 무한반복을 하게 되는데 조금 다른점이 범위에 들어 있고 해당 위치가 미방문 상태라면 방문처리를 해주게 되는데 이 때 selected 배열중에 현재 위치와 같은 즉 조합의 요소 안에 있는 좌표만 방문 처리를 해준다. 만약 얘네가 이어져 있다면 bfs를 다 돌고나서 마지막에 selected 배열의 모든 요소가 map에서 true 여야 한다.
휘융 어렵다 두고두고 포스트 복기해야겠다.
🔵 Ref
