치즈
문제 설명
N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.
<그림 1>
<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.
<그림 2>
<그림 3>
모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.
예제 입력
8 9
0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 1 1 0
0 0 1 1 1 1 1 1 0
0 0 1 1 1 1 1 0 0
0 0 1 1 0 1 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0예제 출력
4문제 풀이
const fs = require("fs");
const path = require("path");
const input = fs
.readFileSync(
process.platform === "linux"
? "/dev/stdin"
: path.join(__dirname, "input.txt")
)
.toString()
.trim()
.split("\n");
const solution = (input) => {
const [N, M] = input[0].split(" ").map(Number);
const arr = input.slice(1).map((line) => line.split(" ").map(Number));
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
// BFS 로 덩어리 찾기
const bfs = () => {
// 공기의 좌표를 찾기 위한 배열
const visited = Array.from({ length: N }, () => Array(M).fill(false));
// 공기 표시
visited[0][0] = true;
// 공기에 인접한 다른 공기들을 찾기 위한 queue 선언
let queue = [[0, 0]];
let head = 0;
while (queue.length > head) {
const [x, y] = queue[head++];
for (let k = 0; k < 4; k++) {
let nx = x + dx[k];
let ny = y + dy[k];
// 인접한 칸 중 공기가 있을 경우
if (0 <= nx && nx < N && 0 <= ny && ny < M) {
// 아직 체크 안되어 있는 공기라면
if (!visited[nx][ny] && arr[nx][ny] === 0) {
// 공기 체크 후 queue에 추가
visited[nx][ny] = true;
queue.push([nx, ny]);
}
}
}
}
// 공기 배열 반환
return visited;
};
// 공기 배열을 매개변수로 받는 녹이기 함수
const melt = (visited) => {
// 원본 배열이 아닌 새로운 배열 선언
const melted = [];
// 2중 반복을 통한 개수 카운팅
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
// 현재 위치가 치즈라면
if (arr[i][j] === 1) {
// 공기를 셀 카운팅 변수 선언
let cnt = 0;
for (let k = 0; k < 4; k++) {
let nx = i + dx[k];
let ny = j + dy[k];
if (0 <= nx && nx < N && 0 <= ny && ny < M) {
// 인접한 칸이 공기라면
if (visited[nx][ny]) {
// 공기 개수 추가
cnt++;
}
}
}
// 녹인 배열에 좌표값 추가
if (cnt >= 2) {
melted.push([i, j]);
}
}
}
}
// 반복문을 통한 배열 값 변경
for (const [x, y] of melted) arr[x][y] = 0;
};
let time = 0;
while (true) {
// 공기에 해당하는 좌표 찾기
let visited = bfs();
// 공기를 통한 치즈 녹이기
melt(visited);
time++;
// 원본 배열 복사해서 모든 요소 값 검사하기
if (arr.flat().every((v) => v === 0)) break;
}
console.log(time);
};
solution(input);아이디어 / 접근법
- 공기가 어떤 곳에 위치해 있는 지 판별하는 BFS 함수
- 공기 배열을 통해 치즈 녹이기 함수
- 원본 배열 복사해서 모든 배열 검사했을 때 녹일 수 있는 치즈가 없다면 결과 리턴
후기
진짜 너무 어려웠음 1시간 넘게 풀다가 GG 쳤고 처음에 나는 치즈 기준으로 인접한 곳이 공기인 지 공기가 아닌 지 판단해서 공기의 수가 2개 이상이면 치즈를 녹이는 방식으로 생각을 했었음 근데 풀다보니 그러면 치즈 내부의 공기는 어떻게 건드리지 않게 할 수 있지? 또 치즈 내부의 공기임을 어떻게 파악할 수 있지? 에 대한 부분에서 막히게 되었다. 그래서 결국 찾아보다가 공기를 기준으로 BFS 를 수행해서 공기에 대한 위치를 가지는 배열을 반환하고 시작 좌표를 무조건 0, 0 으로 고정한 뒤 arr[nx][ny] 값이 0인 경우, 아직 공기인 지 판별되지 않은 경우에만 BFS 탐색을 진행하는 걸로 하였다. 그 후, 녹이기 함수를 통해 현재 칸이 치즈이면서 인접한 칸이 공기일 경우에 카운팅을 해주었고 해당 카운트가 2가 넘어갈 경우 새로운 배열에 좌표값을 추가해주었다. 마지막으로 해당 좌표 값을 통해 실제 배열 값을 변경하는 반복문을 돌리고 로직 부분에서의 while 문을 통해 공기인 지 아닌지 판별하는 bfs 함수 호출과 해당 배열로 실제 치즈를 녹이고 시간 값을 증가하고 배열을 복사하여 모든 요소의 값을 계산해서 모든 요소가 0이라면 즉 치즈가 모두 녹았다면 반복문을 탈출하고 시간 값을 출력해주었다.
진짜 요즘에 BFS 풀면서 다시 벽에 막히는 기분이고 너무 어렵다..