[BOJ] 6907: Floor Plan

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

BOJ - Floor Plan

문제 유형: BFS, DFS, 그래프, 정렬

문제 난이도: Silver I

시간 제한: 1초

메모리 제한: 128MB

 

문제

The floor plan of a house shows rooms separated by walls. This floor plan can be transferred to a grid using the character I for walls and . for room space. Doorways are not shown. Each I or . character occupies one square metre.

In this diagram, there are six rooms.

You have been given the floor plan of a house and a supply of hardwood flooring. You are to determine how many rooms will have the flooring installed if you start installing the floor in the largest room first and move to the next largest room, and so on. You may not skip over any room, and you must stop when you do not have enough wood for the next room. Output the number of rooms that can have hardwood installed, and how many square metres of flooring are left over. No room will be larger than 64 square metres.

The first line contains the number of square metres of flooring you have. The second line contains an integer r in range 1…25 that represents the number of rows in the grid. The third line contains an integer c in 1…25 that represents the number of columns in the grid. The remaining r lines contain c characters of grid data.

 

당신은 방에 정사각형 매트를 깔아야 한다.

방에 다 채울 수 없으면 채우지 않는다.

순서는 가장 크기가 큰 방부터 해서 그 다음으로 큰 방을 채운다.

 

순서를 지켜서 최대 몇 개의 방을 채울 수 있는지와, 남는 매트의 개수를 출력하시오.

 

풀이

2D배열을 받아서 방을 감지하면 BFS를 해서 방의 크기를 구하면 된다.

방은 'I'를 0, .을 1로 해서, 방문처리한 타일은 2로 설정했다.

각 BFS마다 크기를 구해서, 한 배열에 담아놓고, 그 배열을 내림차순 정렬해서 순차적으로 읽으며, 최대 몇 개의 방을 다 채울 수 있고, 남은 타일이 몇개인지를 출력하면 된다.

 

주의할 점은, room이 1개인 경우, rooms가 아닌, room으로 출력해야 한다.

이러한 설명이 문제에는 없어서, 매우 불친절한 문제이긴 하다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

int r, c;
int width;

int bfs(vector<vector<int>> &mat, int row, int col) {
  int size = 1;
  queue<pair<int, int>> q;
  q.push({row, col});
  mat[row][col]++;

  while (!q.empty()) {
    auto curr = q.front();
    q.pop();

    for (int i = 0; i < 4; ++i) {
      int nr = curr.first + dr[i];
      int nc = curr.second + dc[i];

      if (nr < 0 || nr >= r || nc < 0 || nc >= c)
        continue;
      if (mat[nr][nc] == 1) {
        q.push({nr, nc});
        mat[nr][nc]++;
        size++;
      }
    }
  }

  return size;
}

int main(int argc, char *argv[]) {
  cin >> width >> r >> c;

  vector<vector<int>> mat(r, vector<int>(c));
  vector<int> rooms;

  string tmp;
  for (int i = 0; i < r; ++i) {
    cin >> tmp;
    for (int j = 0; j < c; ++j) {
      if (tmp[j] == 'I') {
        mat[i][j] = 0;
      } else {
        mat[i][j] = 1;
      }
    }
  }

  for (int i = 0; i < r; ++i) {
    for (int j = 0; j < c; ++j) {
      if (mat[i][j] == 1) {
        rooms.push_back(bfs(mat, i, j));
      }
    }
  }

  int room_count = 0;
  sort(rooms.begin(), rooms.end(), greater<int>());
  for (int i = 0; i < rooms.size(); ++i) {
    if (rooms[i] > width)
      break;
    else {
      room_count++;
      width -= rooms[i];
    }
  }

  if (room_count == 1) {
    cout << room_count << " room, " << width << " square metre(s) left over\n";
  } else {
    cout << room_count << " rooms, " << width << " square metre(s) left over\n";
  }
  return 0;
}