그래프 (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도 이론상으로는 어느 정도 이해가 가지만, 아직 코드로 구현하기는 쉽지 않은 것 같다.