[백준/node.js] 4963번 섬의 개수

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

4963번: 섬의 개수

 

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

 

 

 

node.js 코드

1. 문제 정리

최근 DFS, BFS 그래프 문제들을 solve 해보기로 결정 했다. 자료구조 공부를 탄탄히 하고 BFS, DFS 문제를 풉시다. 

이 문제는 그래프 탐색 문제로서 정사각형으로 이루어져있는 섬과 바다들의 정보가 들어 있는 지도를 줍니다. 섬의 개수를 세는 프로그램을 작성 하면 되는 간단한 문제일 거 같았다. 유기농 배추 문제와 비슷한 방식으로 풀면 될 거 같았다.

일단 예시 그림부터 살펴보자. 유기농 배추같은 문제는 상 하 좌 우만 탐색 했지만 이번 문제는 대각선까지 탐색 해야하는 문제이다.

예시 그림

다음과 같이 3개가 나오게 된다. 사실 이 문제는 DFS로 해결하든 BFS로 해결 하든 완전 기초 알고리즘만 대입하면 해결 되는 문제이기에 쉬워보일 수 있으나 상대는 js로 입력 받기. 입력량을 보면 다음과 같습니다.

예제 입력 1

이 방대한 양의 숫자들을 받아 graph로 넣는 코드가 DFS로 해결하는 코드보다 길었습니다 ㅠ ㅎㅎ

 

2. 완성 코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : '../ans.txt';
let input = require('fs').readFileSync(filePath).toString().trim().split("\n");
let cntOn =  -1, testCaseWidth = 0, testCaseHeight = 0, graph = [], visited = []

for(let i = 0;; i++){
    input[i] = input[i].split(" ").map((e)=>+e)
    if(cntOn >= 0){
        cntOn++
        for(let j = 0; j < testCaseWidth; j++){
            if(input[i][j] == 1){
                graph[cntOn - 1][j] = 1
            }
        }
        
        if(cntOn == testCaseHeight){
            let ansCnt = 0
            for(let n = 0; n < testCaseWidth; n++){
                for(let m = 0; m < testCaseHeight; m++){
                    if(graph[m][n] == 1 && visited[m][n] == 0){
                        DFS(m, n,testCaseHeight,testCaseWidth)
                        ansCnt++
                    }
                }
            }
            console.log(ansCnt)
            cntOn = -1;
        }
    }
    else{
        testCaseWidth = input[i][0]
        testCaseHeight = input[i][1]
        if(testCaseHeight == 0 && testCaseWidth == 0) break;
        cntOn++
        graph = Array.from(Array(testCaseHeight), () => new Array(testCaseWidth).fill(0))
        visited = Array.from(Array(testCaseHeight), () => new Array(testCaseWidth).fill(0))
    }
}


function DFS(x,y,M,N){
    let dx=[0,1,0,-1,1,1,-1,-1], dy=[1,0,-1,0,1,-1,1,-1]
    visited[x][y] = 1
    for(let i = 0; i < 8; 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, M, N)
            }
        }
    }
}

 

제출 현황

질문 또는 코드 리뷰는 댓글로 부탁드립니다!