연구소
📚 문제 설명
N * M 의 크기의 연구소가 있다.
해당 연구소에서 0은 빈칸, 1은 벽, 2는 바이러스를 의미한다.
바이러스가 상하좌우에 있는 빈칸으로 퍼진다고 했을 때, 벽 2개를 만들어서 바이러스를 최대한 막았을 때, 안전 영역은 몇칸인지 구하는 문제이다.
👨🏻💻 풀이 과정
이 문제가 일반적인 BFS문제와 다른점은 벽을 3개 세웠을 경우를 모두 구하여 BFS를 사용해야 한다는 점이다.
따라서 나는 우선 DFS를 이용하여 벽을 세워준 후에 BFS를 사용하여 주기로 했다.
💡 DFS
벽 세우기 로직은 다음과 같이 구성했다.
DFS(wall)를 이용해 벽을 세운다.- 벽을 3개 세웠을 때,
BFS(map)를 이용해 바이러스를 퍼지게 하고,Find(map, target)를 이용해 0의 갯수를 구해줌. Math.max()를 이용하여 안전 영역의 최댓값을 구해줌.
전체적인 로직
let fs = require("fs");
let input = 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));
// map 에서 내가 원하는 target을 찾아주는 함수
const Find = (map, target) => {
//생략
};
// BFS를 이용하여, 바이러스를 번지게 만든 후, 안전 영역의 수를 리턴.
const BFS = (map) => {
// 생략
};
// 안전 영역의 최댓값을 저장할 변수
let max = 0;
// DFS를 이용하여 벽을 세울 수 있는 모든 경우를 계산
const DFS = (wall) => {
// 만약 벽을 3개 다 세웠을 때
if (wall === 3) {
// MAP을 복사
const newMap = MAP.map(v => [...v]);
// BFS 결과로 안전 영역의 수를 받아줌.
let answer = BFS(newMap);
// 최댓값 확인, 교체
max = Math.max(answer, max);
// 종료
return;
}
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (MAP[i][j] === 0) {
// 벽을 세워줌.
MAP[i][j] = 1;
DFS(wall + 1);
// 재귀를 완료한 후에 벽을 다시 내려야함.
MAP[i][j] = 0;
}
}
}
};
DFS(0);
console.log(max);
💡 BFS
이제 BFS를 이용하여 바이러스를 퍼지게 만들어보자.
Find(map, target)함수를 만들어서map에서target의 위치를 리턴해준다.BFS(map)에 바이러스의 처음 위치를Find(map, target)를 이용해 찾은 후,Queue에 넣어준다.- 일반적인 BFS 반복문을 통해
map에 바이러스가 퍼지게 만들어 준다. Find(map, target)을 이용해 0 의 갯수를 찾아준다.
// map 에서 내가 원하는 값 (target) 을 찾는 함수.
const Find = (map, target) => {
let Queue = [];
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (map[i][j] === target) {
Queue.push([i, j]);
}
}
}
return Queue;
};
const BFS = (map) => {
// 큐에 바이러스 초기 위치를 넣어줌.
let Queue = Find(map, 2);
// shift()를 쓰지 않기 위해 인덱스 번호로 큐를 확인
let idx = 0;
let dx = [1, -1, 0, 0];
let dy = [0, 0, 1, -1];
while (Queue.length > idx) {
const [x, y] = Queue[idx];
// 바이러스가 상하좌우로 움직이며, 0일 경우 퍼지게.
for (let i = 0; i < dx.length; i++) {
const NextX = x + dx[i];
const NextY = y + dy[i];
if (NextX >= 0 && NextY >= 0 && NextX < N && NextY < M) {
if (map[NextX][NextY] === 0) {
map[NextX][NextY] = 2;
Queue.push([NextX, NextY]);
}
}
}
idx++;
}
// Find 를 통해 0의 위치가 배열에 담겨있다. 여기서 길이가 안전 영역의 크기.
return Find(map, 0).length;
};이제 전체 코드를 확인하면 다음과 같다.
전체 코드(주석 X)
let fs = require("fs");
let input = 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 max = 0;
const Find = (map, target) => {
let Queue = [];
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (map[i][j] === target) {
Queue.push([i, j]);
}
}
}
return Queue;
};
const BFS = (map) => {
let Queue = Find(map, 2);
let idx = 0;
let dx = [1, -1, 0, 0];
let dy = [0, 0, 1, -1];
while (Queue.length > idx) {
const [x, y] = Queue[idx];
for (let i = 0; i < dx.length; i++) {
const NextX = x + dx[i];
const NextY = y + dy[i];
if (NextX >= 0 && NextY >= 0 && NextX < N && NextY < M) {
if (map[NextX][NextY] === 0) {
map[NextX][NextY] = 2;
Queue.push([NextX, NextY]);
}
}
}
idx++;
}
return Find(map, 0).length;
};
const DFS = (wall) => {
if (wall === 3) {
const newMap = MAP.map(v => [...v]);
let answer = BFS(newMap);
max = Math.max(answer, max);
return;
}
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (MAP[i][j] === 0) {
MAP[i][j] = 1;
DFS(wall + 1);
MAP[i][j] = 0;
}
}
}
};
DFS(0);
console.log(max);🧐 후기
처음에 벽을 세우는 모든 경우를 다 만들어서 안전 구역을 구하기가 싫어서 다른 방법이 없나 계속 고민하다가 포기하고 다른 풀이를 확인했다.
그런데 다른 코드에서도 벽을 세우는 모든 경우를 다 찾아서 진행하는 것을 보고 그냥 포기하고 모든 벽을 세우는 경우를 구하는 풀이로 풀기 시작했다.
아직 문제의 메모리와 시간 제한만 보고 내 풀이에 확신을 갖지 못하는 것 같다.
JavaScript를 사용하는 모두를 위해...