단지번호붙이기(백준)

108번뇌·2021년 4월 19일
0

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++; 해주는 부분이다.
보통의 지도문제에선 구간이 나눠진건 없었는데
이렇게 섹터나눠진 유형 다룰때는
메인함수 안에 저런식으로 종류배열을 증가시키게 된다.
이해하기

profile
내일 아침 눈을 떳을 때, '기대되는 오늘 하루를 만들기 위해' 나는 오늘도 생각하고 고민한다.

0개의 댓글