[JavaScript] 백준 4963 섬의 개수 (JS)

섬의 개수

📚 문제 설명

섬과 바다가 있는 지도가 주어진다.
상하좌우, 대각선까지는 걸어서 이동할 수 있다고 할 때
섬의 갯수는 몇개인지 구하여라.

👨🏻‍💻 풀이 과정

생각보다 간단한 DFS, BFS 문제인데 최근에 DFS를 안 쓴지 오래된 것 같아서 이번에는 DFS로 풀어보았다.

전체적인 로직은 아래와 같이 구현했다.

• cnt를 DFS() 함수의 인자로 전해준다.
  • cnt를 이용해 visited 배열 체크.
• 섬 중에서 visited 배열이 0인 경우 DFS() 함수 실행.
• DFS() 실행마다 cnt값 +1 증가.
• 최종적으로 cnt 값이 섬의 갯수이다.

    let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
    input = input.map(v => v.split(' ').map(Number));
    let answer = [];
	// 테스트 케이스 진행.
    while (input.length) {
        const [Y, X] = input.shift();
      	// 마지막 "0 0" 입력을 받는다면, 종료.
        if (X ===0 && Y === 0) break;
      	// 섬, 바다 지도.
        const MAP = input.splice(0, X);

        let visited = Array.from({length: X}, _ => Array.from({length: Y}, _ => 0));
      	// 섬갯수 확인할 변수.
        let cnt = 1;
		// DFS 함수.
        const DFS = (nowX, nowY, count) => {
          	// visited 배열 체크.
            visited[nowX][nowY] = count;
          	// 8방향 (12시부터 시계 방향으로)
            const dir = [[-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1]];

            for (const dirElement of dir) {
              	// 다음 위치
                const NextX = nowX + dirElement[0];
                const NextY = nowY + dirElement[1];
              	// 범위 밖이면 넘어가도록
                if (NextX < 0 || NextX >= X || NextY < 0 || NextY >= Y) continue;
                
				// 이어져있는 섬 체크.
                if (!visited[NextX][NextY] && MAP[NextX][NextY] === 1) {
                    DFS(NextX, NextY, count);
                }
            }
        };
		// 전체 MAP을 돌면서 아직 방문하지 않은 섬을 전부 체크.
        for (let i = 0; i < X; i++) {
            for (let j = 0; j < Y; j++) {
                if (!visited[i][j] && MAP[i][j] === 1) {
                  	// cnt 값을 증가 시켜서 섬의 갯수를 확인.
                    DFS(i, j, cnt++);
                }
            }
        }
      	// 마지막 섬을 체크한 후에도 cnt++ 가 진행되기 때문에 -1이 필요.
        answer.push(cnt - 1);
    }
    console.log(answer.join('\n'));

🧐 후기

기본적인 DFS, BFS 문제이지만, 테스트 케이스 때문에 코드가 생각보다 지저분해진 것 같다.