[백준/node.js] 1012번 유기농 배추

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

• 사용언어 : node.js
• 알고리즘 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
• Solved.ac Tier : Silver II

 

문제 설명

 

 

node.js 코드

1. 문제 정리

배추들이 자라는 밭에서 농약을 쓰지 않고 재배하려면 해충으로부터 보호 해야한다고 한다. 배추 지렁이를 두면 해충을 잡아 먹어서 보호 효과가 있다고 한다.

배추 지렁이는 상 하 좌 우로만 움직 일 수 있다. 입력 첫째 줄은 TestCase 값을 주고 그 뒤는 배추를 심은 배추밭의 가로 길이와 세로길이 그리고 배추의 개수를 입력으로 준다. 

 

다음 문제는 BFS또는 DFS로 상 하 좌 우를 탐색해주면 되는 문제이다. 또 상대는 JS이기 때문에 입력 받기가 조금 까다로울 수 있다.

배추 밭의 가로 길이 세로 길이와 심어져 있는 개수를 2개를 받는 코드이다.

이렇게 배추 지렁이를 총 5마리 놔둬야 한다고 한다. 상하 좌우로 이동 할 수 있으면 1이기 때문이다. 

 

2. 완성 코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : '../ans.txt';
let [testCase, ...inputs] = require('fs').readFileSync(filePath).toString().trim().split("\n");
let graph, visited, M, N ,K ,cnt, p = 0
for(let i = 0; i < inputs.length; i++) inputs[i] = inputs[i].split(" ").map((e)=>+e)


for(let i = 0; i < testCase; i++){
    [M, N, K] = inputs[p]
    graph = Array.from(Array(M), () => new Array(N).fill(0)), visited = Array.from(Array(M), () => new Array(N).fill(0))
    cnt = 0
    let temp = p
    for(p = p+1; p <= K + temp; p++){
        let [x, y] = inputs[p]
        graph[x][y] = 1
    }
    for(let j = 0; j < M; j++){
        for(let k = 0; k < N; k++){
            if(graph[j][k] == 1 && visited[j][k]==0){
                DFS(j,k)
                cnt ++
            }
        }
    }
    console.log(cnt)
}

function DFS(x,y){
    let dx=[0,1,0,-1], dy=[1,0,-1,0]
    visited[x][y] = 1
    for(let i = 0; i < 4; i++){
        let ax = x + dx[i], ay = y + dy[i]
        if(ax >= 0 && ay >= 0 && ax < M && ay < N){
            if(visited[ax][ay] == 0 && graph[ax][ay] == 1){
                DFS(ax, ay)
            }
        }
    }
}