문제
세로와 가로의 길이가 모두 N인 마을지도가 배열로 주어졌을 때, '1'은 주민이 있는 집을 의미하고 '0'은 주민이 없는 땅을 의미합니다. 이 마을의 비상연락망 시스템을 구축하려고 합니다. 최초에 정보를 알고 있는 주민의 집들이 '2'로 표시됩니다. 이 중에 일부를 비상 상황 시 비상 연락 요원으로 임명하려고 합니다. 각 담당자들은 정보를 상하좌우 한 칸 바로 옆에 있는 집으로 정보를 전달하기 시작합니다. 정보를 전달받은 주민 역시 한 시간에 상하좌우 한 칸 바로 옆에 있는 집으로 해당 정보를 전달합니다. 비상 연락 요원으로 지정할 수 있는 최대수(num)가 주어질 때, 마을 전체로 정보가 전달되는 데 가장 빠른 시간을 리턴해야 합니다.
입력
인자 1 : village
string타입을 요소로 갖는 배열village.length와village[i].length는 50 이하village[i]는string타입village[i][j]는 세로로 i, 가로로 j인 지점의 정보를 의미village[i][j]는'0','1'또는'2'
인자 2: num
number타입의 10 이하의 양의 정수- 비상 연락 요원으로 지정가능한 최대 수
출력
number타입을 리턴해야 합니다.
주의사항
- 모든 집이 전부 연결되어 있는 것은 아닙니다.
- 요원으로 선택되지 않아도 정보를 전달받은 이상 똑같은 규칙을 따라 정보를 전달해야 합니다.
- 최초에 정보를 알고 있는 주민(
'2')의 수는 10 이하입니다. - village를 그래프로 구현하는 함수가 주어집니다.
입출력 예시
let village = [
'0022', // 첫 번째 줄
'0020',
'0020',
'0220',
];
let num = 1;
let output = gossipProtocol2(village, num);
console.log(output); // --> 0 (이미 모든 주민이 정보를 알고 있는 상태)
village = [
'1001212',
'1201011',
'1102001',
'2111102',
'0012111',
'1111101',
'2121102',
];
num = 5;
output = gossipProtocol2(village, num);
console.log(output); // --> 3-
village의 '2'를 가진 주민을 대상으로 주위에 '1'이 1개이상인 대상을 뽑는다
-
'2'요원의 좌표를 조합으로 num만큼 뽑아준다.
-
조합한 num수만큼의 요원을 대상으로 마을에 소문을 퍼트린다.
-
소문을 퍼트렸을때 전달 안받은 주민이 있으면 무효,
-
모두가 전달받았다면 제일 오래걸린 시간을 리턴한다.
-
조합마다의 시간중 가작 작은 시간을 마지막으로 리턴.
Solution
const createMatrix = (village) => {
const matrix = [];
village.forEach((line) => {
const row = [];
for (let i = 0; i < line.length; i++) row.push(line[i]);
matrix.push(row);
});
return matrix;
};
const gossipProtocol2 = function (village, num) {
const MOVES = [
[-1, 0],
[1, 0],
[0, -1],
[0, 1]
]
let R = village.length;
let C = village[0].length;
let candi = []
const isValid = (a, b) => a >= 0 && a < R && b >= 0 && b < C
for (let i = 0; i < village.length; i++) {
for (let j = 0; j < village[i].length; j++) {
let count = 0
if (village[i][j] === '2') {
MOVES.map((el) => {
let nextR = i + el[0]
let nextC = j + el[1]
if (isValid(nextR, nextC) && village[nextR][nextC] === '1') {
count++
}
})
if (count > 0) candi.push([i, j])
}
}
}
if (!candi.length) return 0
const gossip = (arr, r, c) => {
let queue = [[r, c, 0]]
while (queue.length) {
let [row, col, step] = queue.shift()
if (arr[row][col] === '1' || arr[row][col] > step) {
arr[row][col] = step
step++
MOVES.map((el) => {
let nextR = row + el[0]
let nextC = col + el[1]
if (isValid(nextR, nextC)) {
queue.push([nextR, nextC, step])
}
})
}
}
}
const combination = (arr, len) => {
const results = [];
if (len === 1){
return arr.map((element) => [element]);
}
arr.forEach((fixed, index, origin) => {
const rest = origin.slice(index + 1);
const combinations = combination(rest, len - 1);
const attached = combinations.map((el) => [fixed, ...el]);
results.push(...attached);
});
return results;
}
let answer = Number.MAX_SAFE_INTEGER;
let task = combination([...candi], num)
for (let i = 0; i < task.length; i++) {
let clone = createMatrix(village)
for (let j = 0; j < task[i].length; j++) {
const [x, y] = task[i][j]
gossip(clone, x, y)
}
let max = 0
let check = true
for (let i = 0; i < clone.length; i++) {
if (!check) break
for (let j = 0; j < clone[i].length; j++) {
if (clone[i][j] === '1') {
check = false;
break
}
if (clone[i][j] > max) max = clone[i][j]
}
}
if (check && answer > max) answer = max
}
return answer
};bfs와 combination을 요구하는 문제였다. 처음에 시도해봤던 재귀는 통과하지 않아 queue형태로 바꾸니 시간복잡도가 줄어든듯 하다. 겉으로 보이는 시간복잡도 자체는 같지만 재귀가 호출될때마다 복잡도가 증가하는 듯 하다. 재귀가 편해서 자주 쓰게 되는데 bfs는 queue, stack형식의 솔루션을 사용해야 할 듯.
안녕하세요.