감시
📚 문제 설명
자세한 설명은 문제 링크를 통해 직접 확인하고 간략히 설명하겠다.
총 5 종류의 카메라가 있고 모든 카메라는 90도 각도로 회전할 수 있다.
N * M 크기의 사무실이 주어지고 카메라의 위치와 종류가 주어질 떄,
사무실에서 카메라의 사각지대의 최소 크기를 구하여라.
카메라는 바로 보는 방향에 벽이 없다면 사무실 끝까지 볼 수 있다.
👨🏻💻 풀이 과정
문제를 읽어보면 각각의 카메라가 90도 회전했을 경우를 모두 찾아서 사각지대를 찾으면 되는 것을 알 수 있다.
따라서 각각의 카메라에 대해 모든 경우의 수를 계산하여 조합하면 될 것이다.
전체 로직은 다음과 같은 순서로 구현했다.
- 카메라 위치 저장
[x, y, 카메라 종류] - 카메라의 위치, 방향을 주면 지도에 사각지대를 표시하는 함수
CamOn. - 지도를 확인하여 사각지대 크기를 구할 함수
FindAnswer. - 각각의 카메라의 방향을 정할 재귀 함수
Combination.
전체 풀이
let fs = require("fs");
let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
let [N, M] = input.shift().split(' ').map(Number);
let Map = input.map(v => v.split(' ').map(Number));
// 카메라 위치 저장.
let Cameras = [];
let answer = Infinity;
const CHECK_VALUE = 10;
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (Map[i][j] !== 0 && Map[i][j] !== 6) {
Cameras.push([i, j, Map[i][j]]);
}
}
}
const CamOn = (X, Y, dir, map, isCheck) => {
// 생략.
};
const FindAnswer = (map) => {
// 생략.
};
// 카메라 배열, 타겟이 될 카메라의 인덱스, 지도.
const Combination = (Cams, Index, map) => {
// 재귀 종료 조건.
if (Index === Cams.length) {
const result = FindAnswer(map);
answer = Math.min(result, answer);
return;
}
// 경우의 수를 찾아줄 카메라의 정보.
const [X, Y, Type] = Cams[Index];
if (Type === 1) {
// 생략
} else if (Type === 2) {
// 생략
} else if (Type === 3) {
// 생략
} else if (Type === 4) {
// 생략
} else {
// 생략
}
};
Combination(Cameras, 0, Map);
console.log(answer);💡 CamOn 함수 구현
방향에 대한 값을 배열의 요소로 받아서 진행하기 때문에 상하좌우를 의미할 변수 Direction가 필요하다.
그리고 방향에 대해 현재 위치 X, Y를 변경하며 벽을 만날 때까지 값을 변경하면 된다.
CamOn 함수 코드
const CamOn = (X, Y, dir, map, isCheck) => {
// 상하좌우
const Direction = [[-1, 0], [1, 0], [0, -1], [0, 1]];
// 각각의 방향에 대해 진행.
for (const MyDir of dir) {
// 다음 위치
let [NextX, NextY] = [X + Direction[MyDir][0], Y + Direction[MyDir][1]];
// map 밖으로 벗어나면 안됨, 벽을 만나면 안됨.
while (NextX >= 0 && NextX < N && NextY >= 0 && NextY < M && map[NextX][NextY] !== 6) {
map[NextX][NextY] += isCheck;
// 사무실 끝이나 벽을 만날 때까지 값 변경.
[NextX, NextY] = [NextX + Direction[MyDir][0], NextY + Direction[MyDir][1]];
}
}
};map[NextX][NextY] += isCheck; 로 값을 더해주는 이유는 추후에 Combination 함수에서 재귀를 사용하는데
map 변수를 다시 되돌려 놓을 때 똑같은 값을 - 해주면 되기 때문에 이렇게 구현했다.
FindAnswer함수는 그냥 2중 for문으로 0을 찾으면 되는 간단한 함수이기 때문에 생략하고 바로 Combination 함수 구현을 설명하겠다.
💡 Combination 함수 구현
여기까지 왔으면 이제 Combination 함수의 경우 단순하다.
CamOn 함수에 넣어줄 방향 변수만 직접 넣어주면 끝이기 때문이다.
따라서 아래 과정을 각각의 종류의 카메라에 대해 반복하면 된다.
- 카메라가 보는 방향 값 증가.
CamOn(현재 위치, 카메라 방향, map, 증가시킬 값)
- 재귀 진행.
Combination(카메라 배열, 현재 카메라 인덱스 + 1, map)
- 증가시킨 값을 다시 되돌림.
CamOn(현재 위치, 카메라 방향, map, -증가시킬 값)
Combination 함수 코드
const Combination = (Cams, Index, map) => {
if (Index === Cams.length) {
const result = FindAnswer(map);
answer = Math.min(result, answer);
return;
}
const [X, Y, Type] = Cams[Index];
if (Type === 1) {
CamOn(X, Y, [2], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [2], map, -CHECK_VALUE);
CamOn(X, Y, [3], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [3], map, -CHECK_VALUE);
CamOn(X, Y, [0], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [0], map, -CHECK_VALUE);
CamOn(X, Y, [1], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [1], map, -CHECK_VALUE);
} else if (Type === 2) {
CamOn(X, Y, [2, 3], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [2, 3], map, -CHECK_VALUE);
CamOn(X, Y, [0, 1], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [0, 1], map, -CHECK_VALUE);
} else if (Type === 3) {
CamOn(X, Y, [0,3], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [0,3], map, -CHECK_VALUE);
CamOn(X, Y, [1, 3], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [1, 3], map, -CHECK_VALUE);
CamOn(X, Y, [1, 2], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [1, 2], map, -CHECK_VALUE);
CamOn(X, Y, [0, 2], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [0, 2], map, -CHECK_VALUE);
} else if (Type === 4) {
CamOn(X, Y, [0, 1, 3], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [0, 1, 3], map, -CHECK_VALUE);
CamOn(X, Y, [1, 2, 3], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [1, 2, 3], map, -CHECK_VALUE);
CamOn(X, Y, [0, 1, 2], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [0, 1, 2], map, -CHECK_VALUE);
CamOn(X, Y, [0, 2, 3], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [0, 2, 3], map, -CHECK_VALUE);
} else {
CamOn(X, Y, [0, 1, 2, 3], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [0, 1, 2, 3], map, -CHECK_VALUE);
}
};이제 최종으로 결과 리턴과 FindAnswer 함수를 구현하면 끝이다.
전체 코드
let fs = require("fs");
let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
let [N, M] = input.shift().split(' ').map(Number);
let Map = input.map(v => v.split(' ').map(Number));
// 카메라 위치 저장.
let Cameras = [];
let answer = Infinity;
const CHECK_VALUE = 10;
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (Map[i][j] !== 0 && Map[i][j] !== 6) {
Cameras.push([i, j, Map[i][j]]);
}
}
}
const CamOn = (X, Y, dir, map, isCheck) => {
// 상하좌우
const Direction = [[-1, 0], [1, 0], [0, -1], [0, 1]];
// 각각의 방향에 대해 진행.
for (const MyDir of dir) {
// 다음 위치
let [NextX, NextY] = [X + Direction[MyDir][0], Y + Direction[MyDir][1]];
// map 밖으로 벗어나면 안됨, 벽을 만나면 안됨.
while (NextX >= 0 && NextX < N && NextY >= 0 && NextY < M && map[NextX][NextY] !== 6) {
map[NextX][NextY] += isCheck;
// 사무실 끝이나 벽을 만날 때까지 값 변경.
[NextX, NextY] = [NextX + Direction[MyDir][0], NextY + Direction[MyDir][1]];
}
}
};
const FindAnswer = (map) => {
let result = 0;
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (map[i][j] === 0) {
result++;
}
}
}
return result;
};
// 카메라 배열, 타겟이 될 카메라의 인덱스, 지도.
const Combination = (Cams, Index, map) => {
// 재귀 종료 조건.
if (Index === Cams.length) {
const result = FindAnswer(map);
answer = Math.min(result, answer);
return;
}
// 경우의 수를 찾아줄 카메라의 정보.
const [X, Y, Type] = Cams[Index];
// 총 4가지 경우.
if (Type === 1) {
// 카메라 체크, 재귀, 체크 해제 (반복)
CamOn(X, Y, [2], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [2], map, -CHECK_VALUE);
CamOn(X, Y, [3], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [3], map, -CHECK_VALUE);
CamOn(X, Y, [0], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [0], map, -CHECK_VALUE);
CamOn(X, Y, [1], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [1], map, -CHECK_VALUE);
} else if (Type === 2) { // 총 2가지 경우
CamOn(X, Y, [2, 3], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [2, 3], map, -CHECK_VALUE);
CamOn(X, Y, [0, 1], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [0, 1], map, -CHECK_VALUE);
} else if (Type === 3) {
CamOn(X, Y, [0,3], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [0,3], map, -CHECK_VALUE);
CamOn(X, Y, [1, 3], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [1, 3], map, -CHECK_VALUE);
CamOn(X, Y, [1, 2], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [1, 2], map, -CHECK_VALUE);
CamOn(X, Y, [0, 2], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [0, 2], map, -CHECK_VALUE);
} else if (Type === 4) {
CamOn(X, Y, [0, 1, 3], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [0, 1, 3], map, -CHECK_VALUE);
CamOn(X, Y, [1, 2, 3], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [1, 2, 3], map, -CHECK_VALUE);
CamOn(X, Y, [0, 1, 2], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [0, 1, 2], map, -CHECK_VALUE);
CamOn(X, Y, [0, 2, 3], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [0, 2, 3], map, -CHECK_VALUE);
} else {
CamOn(X, Y, [0, 1, 2, 3], map, CHECK_VALUE);
Combination(Cams, Index + 1, map);
CamOn(X, Y, [0, 1, 2, 3], map, -CHECK_VALUE);
}
};
Combination(Cameras, 0, Map);
console.log(answer);🧐 후기
조합을 어떻게 할지 고민하는데 오래걸린 문제였다.
처음에는 최근에 진행한 톱니바퀴 문제처럼 카메라 방향의 모든 조합을 구한 후에 계산을 할까도 고민했지만, 변수에 저장할 값이 너무 복잡해져서 위의 방법을 사용했다.
JavaScript를 사용하는 모두를 위해...