[BFS] 백준 27737 버섯 농장(서브태스크) JS

[문제출처 | https://www.acmicpc.net/problem/27737 ]

---

💭접근 방식

해당 문제는 Java로 먼저 풀었기 때문에 접근 방식은 이전 포스트로 대체한다.
본진은 자바인데 프론트엔드 직군 코테를 위해 시작한 자바스크립트 풀이도 함께 올린다.

DFS나 BFS를 자바스크립트로 풀며 느낀 조심할 부분은 재귀의 범위가 자바보다 작다는 것이다.
자바에서 통과한 로직을 그대로 자바스크립트로 작성했는데 서브태스크 1만 성공하고 2는 틀렸다.
뭔가 큰 수에서 탐색할 때 문제가 있나 싶어 BFS로도 풀었는데 문제는 다른 곳에 있었다. (풀이 과정에 계속..)

큐에 탐색 칸을 담는 BFS 알고리즘으로 풀기 위해 visited 변수를 추가했다.

---

📝풀이 과정

변수

• visited : 탐색한 map 칸을 구분하기 위한 배열
• class Spore : 탐색 큐에 넣을 포자 정보를 담은 클래스

주요 풀이

• 맵 순회 시, 버섯이 자랄 수 있는 칸이며 방문하지 않은 칸일 때 bfs 탐색을 한다.
  v === 0 && !visited[i][j]
• 탐색 큐에 탐색할 칸의 정보(Spore)를 담고 해당 칸은 방문처리를 한다.
  q.push(new Spore(nr,nc)); visited[nr][nc] = true;
• 각 구역 별 칸 수(area[i])가 연결 가능한 칸 수(K)로 나눠지면 그 몫만큼만 필요하고 그렇지 않을 경우 몫에서 하나 더 필요하다.
  ❗자바와 틀린 결과에 헤맸던 부분, 다른 특성 → 자바스크립트는 자료형 특성 상 정수 나눗셈이라도 결과가 소숫점으로 나오기 때문에 정수 몫을 받고 싶다면 Math.floor()를 사용해야한다!

---

📚참고 자료

[백준,유기농배추| https://www.acmicpc.net/problem/1012 ]

[백준,섬의 개수| https://www.acmicpc.net/problem/4963 ]

---

---

💡정답 코드

결과| 100점, 메모리 11392KB, 시간 164ms

const input = require('fs').readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt').toString().trim().split('\n').map((el) => el.split(' ').map(Number));
let N = input[0][0]; // map 크기
let M = input[0][1]; // 포자 수
let K = input[0][2]; // 연결 수
let map = input.slice(1);
let area = Array(Math.floor(N * N / 2) + 2).fill(0); // 인접한 구역별 칸 수 관리
let visited = Array.from({length: N}, () => Array(N).fill(false));

class Spore {
    constructor(r, c) {
        this.r = r;
        this.c = c;
    }
}
const dr = [-1, 1, 0, 0];
const dc = [0, 0, -1, 1];

// 자원 재정의
map.forEach((row, i) => {
   row.forEach((v, j) => {
       if(v === 1) {
           map[i][j] = -1;
       }
    });
});

let cnt = 0;
map.forEach((row, i) => {
    row.forEach((v, j) => {
        if(v === 0 && !visited[i][j]) {
            bfs(i, j, ++cnt);
        }
    });
});

let needs = 0; // 필요한 포자 수
for(let i = 1; i < area.length; i++) {
    if(area[i] > 0) {
        needs += (area[i] % K === 0 ? Math.floor(area[i] / K) : Math.floor(area[i] / K) + 1);
    }
}

if(cnt > 0 && M >= needs) {
    // cnt > 0: 최소 하나라도 포자를 사용해야 함 조건 체크
    // M >= needs: 가지고 있는 포자 수 내에 필요한 포자 수 가능 체크
    console.log('POSSIBLE');
    console.log(M - needs);
} else {
    console.log('IMPOSSIBLE');
}

function bfs(r, c, idx) {
    let q = [];
    q.push(new Spore(r, c));
    visited[r][c] = true;

    while(q.length > 0) {
        let curr = q.shift();
        let cr = curr.r;
        let cc = curr.c;
        map[cr][cc] = idx;
        area[idx]++;

        for(let d = 0; d < 4; d++) {
            let nr = cr + dr[d];
            let nc = cc + dc[d];

            if(nr < 0 || nc < 0 || nr >= N || nc >= N)
                continue;
            if(!visited[nr][nc] && map[nr][nc] === 0) { // 0이 아닌 구역은 불가지역이거나 탐색된(인덱스 표기)구역
                q.push(new Spore(nr, nc));
                visited[nr][nc] = true;
            }
        }
    }
}

function dfs(r, c, idx) {
    map[r][c] = idx; // map 원본에 구역 인덱스 표기
    area[idx]++; // 해당 구역 인덱스 칸 수 증가

    for(let d = 0; d < 4; d++) {
        let nr = r + dr[d];
        let nc = c + dc[d];

        if(nr < 0 || nc < 0 || nr >= N || nc >= N)
            continue;
        if(map[nr][nc] === 0) { // 0이 아닌 구역은 불가지역이거나 탐색된(인덱스 표기)구역
            dfs(nr, nc, idx);
        }
    }
}

---