https://www.acmicpc.net/problem/2667
#include "stdafx.h"
#include <atlstr.h>
#include <string>
#include <queue>
#include <algorithm>
#include <vector>
#include <iostream>
#include <stdio.h>
using namespace std;
#define MAX_SIZE 25
int Chk[MAX_SIZE][MAX_SIZE];
int Map[MAX_SIZE][MAX_SIZE];
int house_type = 0;
int house[MAX_SIZE];
int DirX[4] = { -1, 0, 1, 0 };
int DirY[4] = { 0, -1, 0, 1 };
vector<int> vTemp;
int n;
bool cmp(int a, int b)
{
return a < b;
}
void BFS(int x, int y) {
queue <pair<int, int >>q;
q.push(make_pair(x, y));
Chk[x][y] = 1;
house[house_type]++;
while (!q.empty()) {
// 큐의 현재 원소를 꺼내기
x = q.front().first;
y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++)
{
int nx = x + DirX[i];
int ny = y + DirY[i];
// 지도를 벗어나지 않고
if ((nx >= 0) && (nx < n) && (ny >= 0) && (ny < n)) {
// 집이면서 방문하지 않았다면 -> 방문
if (Map[nx][ny] == 1 && Chk[nx][ny] == 0) {
Chk[nx][ny] = 1;
// 해당 단지의 집의 수를 증가시킴
house[house_type]++;
// 큐에 현재 nx,ny를 추가
q.push(make_pair(nx, ny));
}
}
}
}
}
int main()
{
scanf_s("%d", &n);
// 지도 데이터 입력
for (int col = 0; col < n; col++) {
for (int raw = 0; raw < n; raw++) {
scanf_s("%1d", &Map[col][raw]);
}
}
// 전체의 지도 데이터를 하나하나 체크
for (int col = 0; col < n; col++) {
for (int raw = 0; raw < n; raw++) {
// 집이 존재하고, 방문하지 않았을 때,
if (Map[col][raw] == 1 && Chk[col][raw] == 0) {
house_type++;
// bfs 탐색 진행
BFS(col, raw);
}
}
}
for (int i = 0; i < MAX_SIZE; i++)
{
if (house[i] > 0)
{
vTemp.push_back(house[i]);
}
}
sort(vTemp.begin(), vTemp.end(), cmp);
// 출력
printf("%d\n", vTemp.size());
for (int i = 1; i < vTemp.size(); i++) {
printf("%d\n", vTemp[i]);
}
return 0;
}
이거 내 코드고 컴파일 에러난다.
VS에서 디버깅 돌리면 답 맞게 나옴.
이 문제에서 주의깊은건
// 전체의 지도 데이터를 하나하나 체크
for (int col = 0; col < n; col++) {
for (int raw = 0; raw < n; raw++) {
// 집이 존재하고, 방문하지 않았을 때,
if (Map[col][raw] == 1 && Chk[col][raw] == 0) {
house_type++;
// bfs 탐색 진행
BFS(col, raw);
}
}
}
전체 BFS함수 호출 이전에
for 루프 두번 돌아가면서 house_type++; 해주는 부분이다.
보통의 지도문제에선 구간이 나눠진건 없었는데
이렇게 섹터나눠진 유형 다룰때는
메인함수 안에 저런식으로 종류배열을 증가시키게 된다.
이해하기