문제 링크
https://www.luogu.org/problemnew/show/P1983문제 설명
단방향 철도 노선 위에 1부터 n까지 번호가 매겨진 역이 있다. 각 역은 최소 1등급 이상의 등급을 가진다. 여러 대의 기차가 이 노선을 운행하며, 각 기차는 다음과 같은 조건을 만족한다: 만약 기차가 역 x를 정류한다면, 출발지와 도착지 사이에 등급이 역 x 이상인 모든 역은 반드시 정류해야 한다. (출발지와 도착지는 이미 정류되는 것으로 간주된다.) 예를 들어, 5대의 기차 운행 정보 중 4대는 조건을 만족하지만, 다섯 번째 기차는 3번 역(2등급)을 정류했지만 경유하는 6번 역(2등급)을 정류하지 않아 조건을 위반한다. 현재 주어진 m개의 기차 운행 정보(모두 조건을 만족)를 바탕으로, 전체 n개의 역이 최소 몇 개의 서로 다른 등급으로 나뉘어야 하는지를 구하라.입력/출력 형식
- 입력 형식: 첫 줄에 두 정수
n,m이 공백으로 분리되어 주어진다. 다음m줄은 각각의 기차 운행 정보를 나타낸다. 각 줄의 첫 숫자는 정류역 수s_i이며, 그 뒤에는 오름차순으로 정류역 번호들이 나온다. - 출력 형식: 가능한 최소 등급 수를 출력한다.
입출력 예시
입력 예시 1:
9 2 4 1 3 5 6 3 3 5 6출력 예시 1:
2
입력 예시 2:
9 3 4 1 3 5 6 3 3 5 6 3 1 5 9출력 예시 2:
3
해결 전략
이 문제는 위상 정렬을 사용하는 것이 핵심이다. 주어진 조건에서 중요한 점은: 어떤 기차가 특정 역을 정류하면, 그 역보다 등급이 같거나 높은 모든 역도 반드시 정류해야 한다는 것이다. 반대로, 정류하지 않은 역은 해당 기차의 정류 역들보다 등급이 낮다는 의미이다. 따라서, 정류하지 않은 역 b는 정류한 역 a보다 등급이 낮아야 하며, 이는 b → a 방향의 간선을 추가함으로써 표현할 수 있다. 즉, 등급이 낮은 역에서 높은 역으로의 방향성 관계를 그래프로 구성한다. 이 과정에서 중요한 최적화는 중복 간선 생성을 방지하는 것이다. 이미 존재하는 간선이면 더 이상 입도를 증가시키지 않아야 하므로, 인접 행렬을 통해 중복 여부를 체크한다. 최종적으로는 위상 정렬을 수행하면서, 각 정점의 등급을 "직전 정점의 등급 + 1"과 현재 등급 중 큰 값을 유지한다. 이는 등급이 단조 증가하도록 보장하며, 결과적으로 최대 등급이 전체 최소 등급 수가 된다. 이 문제의 핵심은 올바른 그래프 구성과 중복 간선 처리이며, 이를 통해 효율적인 위상 정렬을 가능하게 한다.코드 구현 (정답 제출용)
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAX_N = 1005;
int n, m;
int in_degree[MAX_N]; // 각 정점의 진입 차수
int graph[MAX_N][MAX_N]; // 인접 행렬로 그래프 저장
int level[MAX_N]; // 각 역의 등급
bool visited[MAX_N]; // 정류 여부 확인
int stops[MAX_N]; // 현재 기차의 정류역 저장
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int stop_count;
cin >> stop_count;
memset(visited, 0, sizeof(visited));
int start = 0, end = 0;
for (int j = 0; j < stop_count; ++j) {
cin >> stops[j];
visited[stops[j]] = true;
if (j == 0) start = stops[j];
if (j == stop_count - 1) end = stops[j];
}
// 시작지부터 종착지까지의 모든 역 탐색
for (int j = 0; j < stop_count; ++j) {
int current_stop = stops[j]; // 정류한 역
for (int station = start; station <= end; ++station) {
// 정류하지 않은 역이고, 아직 간선이 없는 경우에만 추가
if (!visited[station] && !graph[station][current_stop]) {
graph[station][current_stop] = 1;
in_degree[current_stop]++;
}
}
}
}
// 위상 정렬 초기화: 진입 차수가 0인 정점은 등급 1로 설정
queue<int> q;
for (int i = 1; i <= n; ++i) {
if (in_degree[i] == 0) {
level[i] = 1;
q.push(i);
}
}
int max_level = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 1; v <= n; ++v) {
if (graph[u][v]) {
in_degree[v]--;
level[v] = max(level[v], level[u] + 1);
if (in_degree[v] == 0) {
q.push(v);
}
}
}
max_level = max(max_level, level[u]);
}
cout << max_level << endl;
return 0;
}