[백준] 29634번 Hotel

문제: 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 을 만들 때 사용했다.