백준 1304 (C++) 지역

최초 업로드: 2025-07-25 23:14:43

최근 수정 시간: 2025-07-25 23:14:43

게시자: rlatjwls3333

카테고리: 백준

# [Gold II] 지역

[문제 링크](https://www.acmicpc.net/problem/1304)

## 문제 설명

김형택이 통치하는 빅뱅국은 N개의 도시로 이루어져 있다. 김형택은 초창기에는 탑시, 지용시, 지드래곤시, 승리시, 대성시, 태양시와 같은 이름을 붙였지만, 옆 나라 소시국 (국왕 : 오민식)의 도시 이름을 이길 수 없어서 도시의 이름을 1번부터 N번까지로 바꿨다.

김형택의 국가에는 두 가지 종류의 도로가 있는데, 하나는 일반 도로이고, 또 다른 하나는 고속 도로이다. 고속 도로는 N-1개가 있으며, 1번에서 2번으로 가는 도로, 2번에서 3번으로 가는 도로, i번에서 i+1번으로 가는 도로, N-1번에서 N번으로 가는 도로와 같이 총 N-1개가 있다. 그리고, 몇 개의 일반 도로가 따로 있을 수 있다.

김형택은 이 나라를 몇 개의 지역으로 나누려고 한다. 그리고, 가능하면 많은 지역을 만들려고 한다. 각각의 지역은 모두 같은 수의 도시를 가지고 있어야 하고, 모든 도시는 단 하나의 지역에 속해야 한다. 지역으로 나눌 때에는 다음과 같은 조건을 만족해야 하는데, 지역 A와 지역 B가 다른 지역이라고 가정할 때, A에 속해 있는 어떤 도시에서 B에 속해 있는 어떤 도시로 가는 경로가 있다면, B에 속해 있는 어떤 도시에서 A에 속해 있는 어떤 도시로 가는 경로는 없어야 한다.

입력으로 도시의 개수 N개와 일반 도로의 개수 M개와 그 도로가 주어졌을 때, 김형택이 나눌 수 있는 지역의 개수의 최댓값을 구하는 프로그램을 작성하시오. (일반 도로도 도로다. 고속 도로도 도로다.)

## 입력

첫째 줄에 도시의 개수 N과 일반 도로의 개수 M이 주어진다. 둘째 줄부터 한 줄에 하나씩 일반 도로의 정보가 주어진다. 일반 도로의 정보는 Si Ei와 같이 주어지며, Si에서 Ei로 가는 일반 도로라는 뜻이다. N은 3,000보다 작거나 같은 자연수이다. M은 1,000보다 작거나 같은 자연수이다. 입력으로 주어지는 일반 도로의 정보는 중복되지 않는다.

## 출력

김형택이 나눌 수 있는 지역의 최댓값을 출력한다.

## 풀이
#### 순방향 간선은 이미 있기 때문에, 역방향 간선만 보면서 사이클을 찾으면 된다. 각 사이클의 크기를 분리 집합으로 구해주었다.
#### 지역을 합치는 것은 연속된 구간끼리만 합칠 수 있기에 값을 누적해서 해당 크기로 나눌 수 있는지 확인하였다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int parent[3001], _size[3001];

int _find(int x) {
    if(parent[x]==x) return x;
    return parent[x] = _find(parent[x]);
}

void merge(int x, int y) {
 x = _find(x);
 y = _find(y);
 if(x<y) {
 parent[y] = x;
 _size[x] += _size[y];
 } else if(x>y) {
 parent[x] = y;
 _size[y] += _size[x];
 }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;

// union find로 크기 계산
 for(int i=1;i<=n;i++) {
 parent[i]=i;
 _size[i]=1;
 }

while(m--) {
 int s, e; cin >> s >> e;
 if(s>e) {
 for(int i=e+1;i<=s;i++) merge(e, i);
 }
 }

vector<int> sizes;
 for(int i=1;i<=n;i++) {
 if(parent[i]==i) {
 sizes.push_back(_size[i]);
 }
 }

// 그리디 누적으로 최대 집합수 계산
 for(int i=1;i<=n;i++) {
 int sum=0;
 for(int size : sizes) {
 if(sum==i) sum=0;
 if(sum+size>i) break;
 sum += size;
 }
 if(sum==i) {
 cout << n/i;
 return 0;
 }
 }
}
```