백준 2667 : 단지번호붙이기

💡기본 정보

유형
: DFS/BFS
풀이 날짜
: 2025년 01월 23일 
풀이방법 한줄 요약
: 전체를 순환하면서 상하 좌우를 함께 체크하기 

 

💡문제에서 구해야 할 것

그림 1과 같이 정사각형 모양의 지도가 있음 
1 : 집이 있는 곳
0 : 집이 없는 곳 
철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의 + 단지에 번호를 붙임 
여기서 연결되었다는 것은 어떤 집이 좌우 / 아래위로 다른 집이 있는 경우를 말함 + 대각선에 집이 있는 경우는 연결된 것이 아님

그림2는 그림1을 단지별로 번호를 붙인 것
지도를 입력하여 단지수를 출력 + 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램
- 입력 : 첫 번째 줄에는 지도의 크기 N(정사각형이므로 세로가로 크기가 같음)이 입력
            그 다음 N줄에는 각각 N개의 자료가 입력됨(0과 1) 
- 출력 : 첫 번째 줄에는 총 단지 수를 출력
            그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력

💡알고리즘 설계

- 1을 발견하면 상하 한번 좌우 한번 확인

- 상하나 좌우에서 확인이 되면 방문 표시를 함

- DFS 호출될 때마다 집 갯수 확인(DFS 호출 = 1과 만났음)
- 전체 탐색하며 아파트 단지 갯수 확인

💡CODE

const fs = require("fs");
const input = fs.readFileSync(0,"utf8").toString().split("\n");

const N = parseInt(input[0]);
const graph = input.slice(1).map((v) => v.split("").map(Number));

const apt = [];
let visit = Array.from(Array(N), () => Array(N).fill(false)); 

const row = [0, 0, -1, 1];
const col = [-1, 1, 0, 0];

let CountHome = 0;
let CountComplex = 0;

function DFS(x, y) {
    visit[x][y] = true; 
    CountHome++; 

    for (let i = 0; i < 4; i++) {
        const newX = x + row[i];
        const newY = y + col[i];
        if (
            newX >= 0 &&
            newX < N &&
            newY >= 0 &&
            newY < N &&
            visit[newX][newY]===false &&
            graph[newX][newY] === 1
        ) {
            DFS(newX, newY);
        }
    }
}

for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
        if (graph[i][j] === 1 && visit[i][j]===false) {
            CountHome = 0; 
            DFS(i, j); 
            CountComplex++; 
            apt.push(CountHome); 
        }
    }
}

console.log(
    CountComplex + "\n" + apt.sort((a, b) => a - b).join("\n")
);

 

💡시간복잡도

💡 틀린 이유 & 틀린 부분 수정

조건이 제대로 성립되지 않아서 무조건적으로 재귀호출되어 문제 발생

💡 다른 풀이 or 기억할정보

어제 문제인 1012번 풀이 방법을 활용해서 풀이함

graph[i][j] === 1 && visit[i][j]===false

: DFS 필수 로직