[백준 1012 javascript]유기농 배추(그래프)

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

처음 접근

배추가 심어져 있는 좌표가 주어지고 그 외에는 배추가 심어져 있지 않다.
M-1, N-1 만큼의 이차원 배열을 생성해주고 값을 전부 0으로 초기화한다.
input에서 주어진 좌표들만 1로 선언해준다
인접 좌표를 확인해주는 xval,yval(왼쪽,위,오른쪽,아래) 를 통해 bfs를 구현, 조건에 맞게 문제를 풀어가면 될것같다.
이전에 푼 문제들(미로탐색2178 ,단지 번호붙이기 2667)과 매우 유사해보였다.

내가 푼 풀이

const fs= require('fs')
// const input = fs.readFileSync('../text.txt').toString().trim().split('\n')
const input = fs.readFileSync('dev/stdin').toString().trim().split('\n')
const T = input.shift()
let visited ;
for(let j = 0; j<T;j++)
{
    let result = 0;
    const [M,N,K] = input.shift().split(' ').map(item=>+item)
    //row M, column N만큼의 배추밭 선언, 0으로 초기화
    const field = Array.from({length : M}, ()=> Array(N).fill(0))
    //방문한 노드를 확인하는 이차원 배열 선언
    visited = Array.from({length : M}, ()=> Array(N).fill(false))
    //주어진 배추의 좌표를 1로 초기화
    for(let i =0; i<K;i++)
    {
        let line = input.shift().split(' ').map(item=>+item)
        field[line[0]][line[1]] = 1
    }

    for(let row = 0;row<M;row++)
    {
        for(let column = 0;column<N; column++)
        {
            //방문하지 않았고 배추가 심어져 있다면
            if(visited[row][column] === false && field[row][column] === 1)
            {
                //x좌표, y좌표, 테스트케이스의 field를 넘겨주어 bfs 탐색, 방문한 노드들을 true로 만들어준다
                bfs(row,column,field,M,N)
                //인접해있는 배추들이 몇군데 퍼져있는지 (그래프 순회가 몇번 사용이 됐는지)
                result++
            }
        }
    }

    console.log(result)

}


function bfs(x,y,field,M,N)
{
    //방문할 노드를 확인하는 queue생성
    let needVisit = []
    //파라미터로 받은 최초 x,y push
    needVisit.push([x,y])
    visited[x][y] = true
    //왼쪽, 위, 오른쪽, 아래 순서로 접근할 수 있는 좌표 생성
    const [xval,yval] = [[0,-1,0,1],[-1,0,1,0]]

    while(needVisit.length)
    {
        let currentVertex = needVisit.shift()
        //인접한 좌표값을 계산
        for(let i = 0; i<4;i++)
        {
            //탐색하는 좌표에서의 왼쪽, 위 , 오른쪽, 아래의 좌표 하나씩 탐색
            let [nx,ny] = [xval[i]+currentVertex[0],yval[i]+currentVertex[1]]

            //좌표가 범위를 넘어가지 않을때
            if(nx >=0 && ny >=0 && nx<M && ny <N)
            {
                //(왼쪽,위,오른쪽,아래)탐색하는 노드가 이전에 방문한 적이 없고 배추가 심어져 있을때
                if(visited[nx][ny] === false && field[nx][ny] === 1)
                {
                    //해당 노드를 방문할 노드에 추가
                    needVisit.push([nx,ny])
                    //해당 노드를 방문했다고 추가
                    visited[nx][ny] =true
                }

            }

        }
    }
}

이것도 이전에 푼 문제와 비슷하게
xval과 yval의 반복문(왼쪽,위,오른쪽,아래)을 통해 인접한 좌표를 확인하는 로직만 신경쓰고
bfs를 구현하면 큰 어려움 없이 풀렸다.
주어지는 입력값의 스타일이 조금 달랐지만 이차원 배열을 먼저 선언한 뒤에 입력에서 주어진 좌표에 1을 대입해주면 결국엔 인접좌표 계산을 통해 bfs로 탐색하는 이전의 문제들과 같은 느낌이었다.
1.인접 좌표를 선언한뒤
2.인접 좌표들에 대한 반복문을 돌리며
3. 좌표 범위가 넘어가지 않는 if문
4. 탐색하는 노드가 이전에 방문한적이 없는지, 그 노드가 탐색 대상인지 (1인지) 확인

풀다보니 이런 비슷한 유형이 많은것같다.

끝!