문제 링크
https://www.acmicpc.net/problem/1012
풀이 전략
특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.
배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다
코드
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const input = [];
let idx = 0;
rl.on("line", function (line) {
input.push(line.split(" ").map(Number));
}).on("close", function () {
solution(input);
process.exit();
});
const solution = (arr) => {
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
const t = arr[idx++][0];
const answer = [];
for (let i = 0; i < t; i++) {
const [m, n, k] = arr[idx++];
const field = Array.from({ length: m }, () => Array(n).fill(0));
let cnt = 0;
for (let j = 0; j < k; j++) {
const [x, y] = arr[idx++];
field[x][y] = 1;
}
for (let a = 0; a < m; a++) {
for (let b = 0; b < n; b++) {
if (field[a][b]) {
cnt++;
dfs(a, b);
}
}
}
answer.push(cnt);
function dfs(x, y) {
if (!field[x][y]) return;
field[x][y] = 0;
for (let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if (0 <= nx && nx < m && 0 <= ny && ny < n && field[nx][ny]) {
dfs(nx, ny);
}
}
}
}
console.log(answer.join("\n"));
};
회고
dfs로 붙어있는 배추들을 모두 탐색하고 이중 for문을 돌면서 다른 군락들을 찾으면 풀 수 있다. dfs를 구현할줄 알고 입력과 출력을 자세히 살피면 풀 수 있는 문제. 더 좋은 dfs 방법이 있을 것 같은데 아직 내 실력으로는 역부족이다.
더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)
'Algorithm > 백준[BOJ]' 카테고리의 다른 글
[JS] 백준 1697번 숨바꼭질 (0) | 2022.06.07 |
---|---|
[JS] 백준 7569번 토마토 (0) | 2022.06.07 |
[JS] 백준 7576번 토마토 (0) | 2022.06.06 |
[JS] 백준 2178번 미로 탐색 (0) | 2022.06.06 |
[JS] 백준 2667번 단지번호붙이기 (0) | 2022.06.05 |
댓글