🧠𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/💛 백준
[백준/그래프탐색] 1743번. 음식물피하기(JavaScript)
안오늘
2021. 8. 30. 20:36
문제설명
https://www.acmicpc.net/problem/1743
2667번 단지번호붙이기와 비슷하게 푸는 DFS문제이다.
문제풀이
const fs = require("fs");
let input = fs.readFileSync("../test.txt").toString().split("\n");
let NMK = input.shift().split(' ').map(el => parseInt(el, 10));
const N = NMK.shift();
const M = NMK.shift();
const K = NMK.shift();
let graph = Array.from(new Array(N), () => new Array(M).fill(0));
for (let i = 0; i < K; i++) {
const [row, col] = input[i].split(' ').map(el => parseInt(el, 10) - 1);
graph[row][col] = 1; // 음식물 쓰레기가 있는 곳을 1이라 표기
}
let count = 0;
const dfs = (i, j) => {
const dx = [1, 0, -1, 0];
const dy = [0, 1, 0, -1];
if (rangeCheck(i, j) && graph[i][j] === 1) {
graph[i][j] = 0; //방문처리
count += 1;
for (let k = 0; k < dx.length; k++) {
dfs(i + dx[k], j + dy[k]);
}
}
}
const rangeCheck = (i, j) => {
if (i >= 0 && i < N && j >= 0 && j < M) {
return true;
} else return false;
}
const solution = () => {
let trashCnt = [];
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (graph[i][j] === 1) { // 음식물 쓰레기가 있는 곳이면 dfs탐색
dfs(i, j);
trashCnt.push(count);
count = 0;
}
}
}
trashCnt.sort((a, b) => b - a); //오름차순 정렬
return trashCnt[0];
}
console.log(solution());