[백준] 29634번 Hotel

2025. 5. 9. 12:46·백준 문제/BFS

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

'백준 문제/BFS' 카테고리의 다른 글
  • [백준] 21736번 헌내기는 친구가 필요해
  • [백준] 13265번 색칠하기
  • [백준] 2667번 단지번호붙이기
  • [백준] 2206번 벽 부수고 이동하기
dubu0721
dubu0721
dubu0721 님의 블로그 입니다.
  • dubu0721
    dubu0721 님의 블로그
    dubu0721
  • 전체
    오늘
    어제
    • 분류 전체보기 (335)
      • 프로그래밍언어론 정리 (0)
      • 컴퓨터네트워크 정리 (5)
      • 알고리즘&자료구조 공부 (64)
        • it 취업을 위한 알고리즘 문제풀이 입문 강의 (60)
        • 학교 알고리즘 수업 (3)
        • 실전프로젝트I (0)
      • 백준 문제 (193)
        • 이분탐색 (7)
        • 투포인트 (10)
        • 그래프 (7)
        • 그리디 (24)
        • DP (25)
        • BFS (15)
        • MST (7)
        • KMP (4)
        • Dijkstra (3)
        • Disjoints Set (4)
        • Bellman-Ford (2)
        • 시뮬레이션 (3)
        • 백트래킹 (15)
        • 위상정렬 (5)
        • 자료구조 (25)
        • 기하학 (1)
        • 정렬 (11)
        • 구현 (8)
        • 재귀 (8)
        • 수학 (8)
      • 유니티 공부 (11)
        • 레트로의 유니티 게임 프로그래밍 에센스 (11)
        • 유니티 스터디 자료 (0)
        • C# 공부 (0)
      • 유니티 프로젝트 (48)
        • 케이크게임 (13)
        • 점토게임 (35)
      • 언리얼 공부 (10)
        • 이득우의 언리얼 프로그래밍 (10)
      • 진로 (1)
      • 논문 읽기 (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    골드메탈
    오블완
    맵
    수학
    바킹독
    백트래킹
    유니티 프로젝트
    우선순위큐
    그래프
    시뮬레이션
    투포인터
    언리얼
    정렬
    그리디
    해시
    재귀
    dp
    티스토리챌린지
    큐
    C#
    자료구조
    이벤트 트리거
    유니티 공부 정리
    유니티
    이득우
    이분탐색
    레트로의 유니티 프로그래밍
    백준
    BFS
    스택
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
dubu0721
[백준] 29634번 Hotel
상단으로

티스토리툴바