BOJ
BOJ::14567 선수과목
BOJ Gold 5
BOJ::14567 선수과목
[BOJ] : https://www.acmicpc.net/problem/14567
- Level : Gold 5
시사점
- 문제 제목 그대로, 선수 과목에 대한 탐색 문제입니다.
- dp, BFS 등 여러가지 풀이가 있을 것으로 예상됩니다.
이해(4)
- 현재 과목의 선수과목이 모두 수강된 경우 현재 과목을 수강완료 처리합니다.
설계(3)
- 단순 로직으로 설계하였습니다.
- 현재 과목과 연관된 선수과목 List를 가지고 있고, 해당 List가 모두 끝난 경우 현재 과목에 대한 done처리를 해 줍니다.
시간 복잡도
- 최악의 경우 한 학기에 한 과목만 수강할 수 있다고 할 때, N이 최대 1000 이므로,
- O(N * N - 1 * N)으로 예상됩니다.
- 과목 수 * 인접 과목 수 * 총 semester
공간 복잡도
구현(15)
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1000+1;
int n, m;
int doneWhen[MAX_N];
vector<int> adj[MAX_N];
void solve(){
int sem = 1;
while(true){
bool doneOuter = true;
for(int i = 1; i <= n; i++){
bool doneInner = true;
if(doneWhen[i] != 0) continue;
if(adj[i].size() == 0){
doneOuter = false;
doneWhen[i] = sem;
continue;
}
for(int j = 0; j < adj[i].size(); j++){
int pre = adj[i][j];
if(doneWhen[pre] == 0 || doneWhen[pre] == sem){
doneOuter = false;
doneInner = false;
break;
}
}
if(doneInner == true){
doneOuter = false;
doneWhen[i] = sem;
}
}
if(doneOuter == true)
break;
sem++;
}
for(int i = 1 ; i <= n; i++){
if(i != n) cout << doneWhen[i] <<" ";
else cout << doneWhen[i]<<endl;
}
}
int main(){
freopen("input.txt", "r", stdin);
cin >> n >> m;
for(int i = 0; i < m; i++){
int x, y;
cin >> x >> y;
adj[y].push_back(x);
}
solve();
return 0;
}
디버깅(x)
좋은 코드
- djm03178 님의 공개 코드를 가져왔습니다.
- dp로 푸신 방법이 매우 깔끔 및 간단하여 배울점이 많다고 생각합니다.
for(int x : adj[i])
ret = max(ret, f(x));
return ++ret;
- 인접 원소에 대해 먼저 모두 완료 시키고, 인접 원소가 모두 완료된 경우 ++을 시켜 현재 과목을
완료시킵니다.
- 즉, 인접 과목중 가장 늦은 학기에 끝난 과목의 학기+1 을 현재 과목의 완료 시점으로 갖습니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dp[1001];
vector<int> adj[1001];
int f(int i)
{
int &ret = dp[i];
if (ret)
return ret;
for (int x : adj[i])
ret = max(ret, f(x));
return ++ret;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, i;
cin >> n >> m;
while (m--)
{
int a, b;
cin >> a >> b;
adj[b].push_back(a);
}
for (i = 1; i <= n; i++)
cout << f(i) << ' ';
}