그래프 (BFS) 문제 #2

그래프 BFS (영역 구하기) 문제풀이

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

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

입력
첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다

---

풀이방향

• 먼저 주어진 가로 세로 길이로 2차원배열을 만들어준다.

• 배열을 초기화시켜준다.

• 주어진 좌표로 직사각형을 그려준다.

• 2차원 배열을 모두 순회하면서 ,bfs를 실행해준다.

• bfs를 이용한다.
  (1) 큐를 초기화하고 시작 위치를 지정
  (2) 방문한 위치를 1로 표시
  (3) 상하좌우를 확인하고, 인접한 칸을 확인한다.
  (4) 큐가 비게 될 떄까지 탐색을 한다.
  (5) 탐색한 넓이도 ++1신켜준다.

• 여역의 넓이들을 보여주고, 개수를 출력해준다.

const input = `5 7 3
0 2 4 4
1 1 2 5
4 0 6 2`.split("\n");

// M: 모눈종이의 세로 크기
// N: 모눈종이의 가로 크기
// K: 직사각형의 개수
const [M, N, K] = input[0].split(" ").map(Number);

// 배열 초기화
const grid = Array.from(Array(M), () => Array(N).fill(0));

// 직사각형들을 그립니다.
for (let i = 1; i <= K; i++) {
  // (x1 , y1) => (x2,y2)가 꼭지점에서 꼭지점 위치
  const [x1, y1, x2, y2] = input[i].split(" ").map(Number);
  // 각 직사각형의 좌표를 읽어서 해당 범위를 1로 채웁니다 (1은 직사각형이 있는 부분을 의미)
  for (let y = y1; y < y2; y++) {
    for (let x = x1; x < x2; x++) {
      grid[y][x] = 1; // 직사각형이 있는 부분을 1로 표시
    }
  }
}

// 상하좌우로 이동하기 위한 방향 벡터
const directions = [
  [-1, 0], // 상
  [1, 0], // 하
  [0, -1], // 좌
  [0, 1], // 우
];

// 주어진 좌표가 모눈종이 내부에 있는지 확인하는 함수
const inBounds = (x, y) => x >= 0 && x < N && y >= 0 && y < M;

// BFS(너비 우선 탐색)를 사용하여 직사각형 외부의 영역을 탐색하는 함수
function bfs(startX, startY) {
  // 탐색을 위한 큐를 초기화하고 시작 위치를 큐에 추가
  let queue = [[startX, startY]];
  grid[startY][startX] = 1; // 방문한 위치는 1로 표시하여 다시 방문하지 않도록 합니다.
  let areaSize = 0; // 현재 영역의 넓이

  // 큐가 빌 때까지 탐색
  while (queue.length > 0) {
    const [x, y] = queue.shift(); // 큐에서 현재 위치를 꺼냄
    areaSize++; // 현재 영역의 넓이를 1 증가

    // 상하좌우의 인접한 칸을 확인
    for (const [dx, dy] of directions) {
      const newX = x + dx;
      const newY = y + dy;

      // 새로운 좌표가 모눈종이 내에 있고, 아직 방문하지 않은(0인) 경우
      if (inBounds(newX, newY) && grid[newY][newX] === 0) {
        grid[newY][newX] = 1; // 방문 처리
        queue.push([newX, newY]); // 큐에 추가하여 다음 탐색 대상으로 설정
      }
    }
  }

  return areaSize; // 탐색한 영역의 넓이를 반환
}

let areas = []; // 각 분리된 영역의 넓이를 저장할 배열

// 모눈종이의 모든 칸을 순회하면서
for (let y = 0; y < M; y++) {
  for (let x = 0; x < N; x++) {
    // 아직 방문하지 않은(0인) 칸이 있다면 새로운 영역으로 간주하고 BFS 수행
    if (grid[y][x] === 0) {
      areas.push(bfs(x, y)); // 새로운 영역의 넓이를 계산하여 areas 배열에 추가
    }
  }
}

// 분리된 영역의 넓이를 오름차순으로 정렬
areas.sort((a, b) => a - b);

// 분리된 영역의 개수와 각 영역의 넓이를 출력
console.log(areas.length);
console.log(areas.join(" "));

---

마무리

• BFS도 이론상으로는 어느정도 이해가 가지만, 아직 코드로 구현에는 쉽지 않은 것 같다.