[백준 2667 javascript]단지번호붙이기(그래프)

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

문제 접한 후 처음 접근

좌표내에 연결된 단지 모임들의 개수를 구하는 문제이다.

N이 최대 25이므로 25x25의 좌표들을 반복문을 돌려도 무방해보였다.

해당 좌표를 방문하지 않았다면 bfs를 통해 연결된 단지의 노드들을 방문했다고 처리하고, 방문한 노드만큼 +1을 visited에 추가해주어 단지모임의 총 개수를 구한다.

bfs 순회가 종료되면 visited를 0으로 초기화하고 다시 반복문을 돌며 visited가 0이 아니라면 bfs, 0이라면 continue를 통해 답을 구하면 될것같다.

구현

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 n = Number(input.shift())
const apart = []
//아파트 이차원 배열 선언
for(let i = 0; i<input.length;i++)
{
    apart.push(input[i].split('').map(item=>+item))
}

//방문한 노드와 단지모임의 총 개수를 계산해주는 변수,최초 0으로 초기화
let visited = Array.from({length : n}, ()=>Array(n).fill(0))

//인접한 좌표를 계산해주는 변수([xval,yval] 왼쪽, 위, 오른쪽, 아래 순서)
const [xval,yval] = [[-1,0,1,0],[0,1,0,-1]]
let groupCount = 0
let result = []
let apartNumber;
for(let i = 0; i< n;i++)
{
    for(let j=0;j<n;j++)
    {
        //방문하지 않았고 아파트가 존재한다면
        if(visited[i][j] ===0 && apart[i][j] === 1)
        {
            //좌표마다 bfs 순회
            apartNumber = bfs(i,j)
            result.push(apartNumber)
            groupCount++
        }
    }
}

bfs(0,1)

function bfs(x,y)
{
    const needVisit = []
    needVisit.push([x,y])
    visited[x][y] = 1
    let count = 1;

            //bfs 순회
    while(needVisit.length>0)
    {
        const currentApart = needVisit.shift()

        for(let i = 0; i<4;i++)
        {
            //시작 노드에서 인접 노드 (왼쪽, 위, 오른쪽, 아래)계산
            const [nx,ny] = [currentApart[0]+xval[i],currentApart[1]+yval[i]]

            //인접한 x,y의 좌표가 0보다 크거나 같고 n보다 작을때 (존재하는 좌표 범위 내에 있을때)
            if(nx >=0 && ny>=0 && nx<n && ny<n)
            {
                //아파트가 있을떄 (값이 1일때), 방문하지 않은 노드일때
                if(apart[nx][ny] === 1 && visited[nx][ny] === 0 )
                {
                    count++
                    visited[nx][ny] = visited[nx][ny]+ count
                    needVisit.push([nx,ny])
                }
            }
        }

    }
    return count
}

console.log(groupCount)
console.log(result.sort((a,b)=>{return a-b}).join('\n'))

코드 풀이

입력과 변수 받기

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 n = Number(input.shift())
const apart = []
//아파트 이차원 배열 선언
for(let i = 0; i<input.length;i++)
{
    apart.push(input[i].split('').map(item=>+item))
}

input을 split 함수와 map함수를 통해 apart 일차원 배열에 일차원 배열을 push하는 방식으로 apart 이차원 배열을 만들어줬다.

//방문한 노드와 단지모임의 총 개수를 계산해주는 변수,최초 0으로 초기화
let visited = Array.from({length : n}, ()=>Array(n).fill(0))

방문할 노드를 확인하는 이차원 배열을 모두 0으로 초기화 해줬다.
알면 굉장히 유용한 이차원 배열 선언 방법!

//인접한 좌표를 계산해주는 변수([xval,yval] 왼쪽, 위, 오른쪽, 아래 순서)
const [xval,yval] = [[-1,0,1,0],[0,1,0,-1]]
let groupCount = 0
let result = []
let apartNumber;

이전에 풀었던 미로탐색 문제에서 사용한 방식이다.
인접한 좌표를 계산할 수 있는 x,y좌표를 미리 선언해주고 반복문을 사용해주면서 가독성을 키웠다.

그래프 순회 함수 (BFS)

function bfs(x,y)
{
    const needVisit = []
    needVisit.push([x,y])
    visited[x][y] = 1
    let count = 1;

            //bfs 순회
    while(needVisit.length>0)
    {
        const currentApart = needVisit.shift()

        for(let i = 0; i<4;i++)
        {
            //시작 노드에서 인접 노드 (왼쪽, 위, 오른쪽, 아래)계산
            const [nx,ny] = [currentApart[0]+xval[i],currentApart[1]+yval[i]]

            //인접한 x,y의 좌표가 0보다 크거나 같고 n보다 작을때 (존재하는 좌표 범위 내에 있을때)
            if(nx >=0 && ny>=0 && nx<n && ny<n)
            {
                //아파트가 있을떄 (값이 1일때), 방문하지 않은 노드일때
                if(apart[nx][ny] === 1 && visited[nx][ny] === 0 )
                {
                    count++
                    visited[nx][ny] = visited[nx][ny]+ count
                    needVisit.push([nx,ny])
                }
            }
        }

    }
    return count
}

일반적인 BFS 코드에 인접한 좌표를 계산하는 로직과 조건문, 그리고 결과값을 계산하는 로직을 추가한다.

xval과 yval의 반복문(왼쪽,위,오른쪽,아래)을 통해 인접한 좌표를 확인
각각의 인접한 좌표마다
1. 좌표 범위 내에 있는지 확인하는 if문
2. 그 좌표에 아파트가 있는지 확인하고, 이전에 방문하지 않은 노드인지 확인하는 if문

의 조건을 만족했을때 인접한 노드들을 통해 bfs가 얼마나 순회하는지 확인하는 count를 늘려주면서 인접한 아파트 모임내의 아파트 개수를 구해주었다. 그후 count를 반환.

결과값 출력

for(let i = 0; i< n;i++)
{
    for(let j=0;j<n;j++)
    {
        //방문하지 않았고 아파트가 존재한다면
        if(visited[i][j] ===0 && apart[i][j] === 1)
        {
            //좌표마다 bfs 순회
            apartNumber = bfs(i,j)
            result.push(apartNumber)
            groupCount++
        }
    }
}

bfs(0,1)
console.log(groupCount)
console.log(result.sort((a,b)=>{return a-b}).join('\n'))

n의 크기가 최대 25이기 때문에 모든 좌표를 확인해봐도 무방하다고 판단을 했고, 어쩌피 bfs로 순회한 좌표는 if문에 걸리지 않기 때문에 시간 복잡도가 크지 않을것이다.

반복문에 걸린 if문을 groupCount++을 해주어 아파트 모임의 개수를 구해주고

인접한 아파트 모임내의 아파트 개수를 반환한 결과를 배열에 넣어 오름차순으로 정렬하여 값을 출력하였다.

걸린부분

 if(nx >=0 && ny>=0 && nx<n && ny<n)
            {
                //아파트가 있을떄 (값이 1일때), 방문하지 않은 노드일때
                if(apart[nx][ny] === 1 && visited[nx][ny] === 0 )
                {
                    count++
                    visited[nx][ny] = visited[nx][ny]+ count
                    needVisit.push([nx,ny])
                }
            }

이 부분에서 visited[nx][ny] === 0 (이전에 방문하지 않은 노드인지 확인) 를 추가해주지 않아 시간을 많이 잡아먹었다. 이 부분을 다음부터 신경써야겠다.
추가적으로 visited 배열을 굳이 count로 하지 않고 boolean으로 나타내도 좋을듯 !

정리
1.이차원 배열 선언하는 방법 기억하기
let visited = Array.from({length : n}, ()=>Array(n).fill(0))
2.const [xval,yval] = [[-1,0,1,0],[0,1,0,-1]] 룰 활용한 인접 좌표 확인
3.조건문을 달때 방문하지 않은 노드인지 확인하는 부분 신경쓰기

끝!