문제: 29634번: Hotel
#include <bits/stdc++.h>
using namespace std;
vector<vector<char>> board;
vector<vector<bool>> visits;
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
int n, m; // 높이, 너비
long long BFS(pair<int, int> start) {
long long size = 0;
queue<pair<int, int>> nexts;
nexts.push(start);
visits[start.first][start.second] = true;
while (!nexts.empty()) {
pair<int, int> cur = nexts.front();
nexts.pop();
size++;
for (int i = 0; i < 4; i++) {
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if (nx < 0 || nx > n - 1 || ny <0 || ny > m - 1) continue;
if (visits[nx][ny] == true || board[nx][ny] == '*') continue;
nexts.push({ nx, ny });
visits[nx][ny] = true;
}
}
if (size == 0) {
size = -1;
}
return size;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
board = vector<vector<char>>(n, vector<char>(m));
visits = vector<vector<bool>>(n, vector<bool>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> board[i][j];
}
}
long long ans = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (visits[i][j] == true || board[i][j] == '*') continue;
long long size = BFS({ i, j });
if (size > ans) {
ans = size;
}
}
}
cout << ans << "\n";
return 0;
}
아나 처음에 visits 이름을 visit 으로 선언했다가 bits/stdc++.h 에 있는 visit 이랑 중복돼서 컴파일 에러 떴다;;;; 열받네
아무튼 문제에서 원하는 거는 방의 최대 크기를 구하는 거니까 일단 main 에서 이중포문으로 각 위치를 BFS 돌리도록 했다. 물론 방문한 적이 없어야 하고, 복도가 아니어야 BFS 를 돌릴 수 있도록 했다.
BFS 에 진입하면 큐에 시작 지점을 넣고, while 문으로 큐가 다 빌때까지 돌도록 했다. 상하좌우가 인접한 공간이라고 문제에서 주어졌으므로 dx, dy 배열을 만들어놓고 nx, ny 을 만들 때 사용했다.