BOJ(백준) 30831번 선후수과목

https://www.acmicpc.net/problem/30831

2023 uospc(서울시립대 컴퓨터과학부 알고리즘 경진대회) div2의 최고 난이도 문제이다. 직접 참가했던 대회이니만큼 대회에 관해 얘기를 조금 하자면,

큰 대회가 아닌지라 당시 꽤나 자신만만히 대회에 참가했었는데 아쉽게 2등으로 대회를 마무리했다. 못 풀었던 문제 전부가 알고보니 상당히 스탠다드하거나 웰노운한 문제, 알고리즘의 변형이었는데 항상 새롭고 더 어려운 알고리즘을 공부하는데 급급해 기초적인 알고리즘의 문제를 다양히 경험해보지 않았고 코드 포스와 같은 실전 경험의 부족이 성적 부진의 원인이라는 것을 깨달아 그 뒤로 해당 방면을 더욱 열심히 공부하는 계기가 되었다.

기회가 된다면 다음에 uospc에 또 참가하여 1등을 노릴 것이다.

아무튼 잡설은 여기까지 하고 문제를 풀면서 했던 생각의 흐름은 다음과 같다

ⓐ 우선 입력받은 강의를 듣기 위한 가장 우선적인 필수 선수 과목을 찾아야 된다(필수 선수 과목이 없을 때까지 계속 거슬러 올라가서 찾을 수 있다). 한 강의의 필수 선수 과목은 하나 이하이므로 여러 경로로 갈라질 일은 없다.

ⓑ 그 이후 필수이든 권장이든 해당 과목의 후수 과목으로 쭉 내려가다가 듣지 않은 강의를 발견하면 그 강의를 출력하면 된다. 만약 강의의 후수 강의가 없는데 그 강의를 들었다면 -1을 출력한다. 이 또한 마찬가지로 한 강의의 후수 과목은 하나 이하이므로 경로는 하나만 존재한다.

이제 이것을 구현하기만 하면 된다.

문제를 읽어보니 문제 해결에 필요한 기저가 되는 알고리즘은 분리 집합과 유니온 파인드가 적합해 보인다. ⓐ는 유니온 파인드의 파인드 함수를 그대로 사용하면 될 것 같고 ⓑ는 약간의 변형이 필요해 보인다.

문제를 풀기 위해서 부모 배열(par), 자식 배열(chi), 체크 배열(check) 이렇게 3가지의 배열을 만들 것이다.

부모 배열은 ⓐ를 위한 배열로 강의의 필수 선수 과목을 저장하고, 자식 배열은 ⓑ를 위한 배열로 강의의 후수 과목(필수, 권장), 체크 배열은 해당 강의를 들었는지 기록한다(1이면 강의를 들은 것, 0이면 강의를 듣지 않은 것).

ⓐ에서 권장 선수 과목은 관련이 없기 때문에 필수 선수 관계를 입력 받을 때만 사용한다. (예를 들어 i의 필수 선수 과목이 k라면 par[i]=k)

필수 선수 과목이 없다면 부모배열에 본인으로 저장한다.

ⓑ에서는 권장이든 필수든 둘 다 관련이 있기 때문에 필수와 권장을 입력받을 때 둘 다 사용한다. (예를들어 k의 필수or권장 선수 과목이 i라면 chi[i]=k)

후수 과목이 없다면 자식 배열에 -1로 저장한다.

이제 두 개의 함수를 만들어 준다.

int find1(int a) {
	if(par[a]==a) return a;
	return par[a]=find1(par[a]);
}

위는 ⓐ에서 사용할 함수로 가장 우선적인 필수 선수 과목을 찾고 다음 계산을 줄이기 위해 경로를 갱신한다.

int find2(int a) {
	if(!check[a]||!chi[a]) return a;
	return chi[a]=find2(chi[a]);
}

위는 ⓑ에서 사용할 함수로 들은 적이 없거나 후수 과목이 없으면 그 값을 리턴하고 마찬가지로 다음 계산을 줄이기 위해 경로를 갱신한다. 이후 체크 배열에서 해당 값을 확인해보면 강의를 들을 수 있는지 확인이 가능하다.

cin>>t1;
find2(find(t1));
if(!check[t1]) {
	check[t1]=1;
    cout<<t1<<"\n";
} else cout<<"-1\n";

두 함수를 사용해 입력받은 강의를 find1한 값을 다시 find2에 넣고 리턴 된 강의가 들은 적이 없는 강의면 해당 강의를 출력하고 체크 배열에 1로 저장, 들은 적이 있으면 -1을 출력하도록 코드를 만들었다.

하지만 제출 결과는 다음과 같았다.

논리가 완벽하다고 생각했기 때문에 원인이 뭔지 꽤 오랜시간 헤맸는데 문제를 잘 읽어보니 한 강의의 필수 선수 과목과 후수 과목은 하나 이하이지만 권장 선수 과목은 별개로 더 존재할 수 있었던 것이다(여러 강의가 해당 강의를 후수 과목으로 지목).

맨 처음에 입력받은 강의의 필수 선수 과목 라인에 내가 함수를 통해 찾은 과목이 있다면 상관이 없지만 만약 내가 처음에 입력받은 강의의 후수 과목이 최종 선택이 됐다면 해당 강의의 필수 선수 과목이 따로 존재하는지 체크를 해줘야된다.

이를 해결해 주기 위해서 위의 함수를 통해 찾은 강의를 들을 수 있다면 그 강의의 필수 선수 과목이 있는지 체크하고 있다면 그 강의를 듣도록 위의 코드를 한 번 더 반복해주었다.

처음에 함수를 통해 찾은 강의는 해당 강의의 필수 선수 과목이 남아있지 않다면 무조건 그 강의를 들을 수 있으므로(즉, 해당 강의는 듣지 않았으므로) 그 강의 후수 과목 라인에 있는 것들이 선택될 일은 없다.

따라서 함수를 2번 돌리는 것으로 충분하다.

AC code

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

int par[1000001],check[1000001],chi[1000001],N,A,B,t1,t2,S;

int find1(int a) {
	if(par[a]==a) return a;
	return par[a]=find1(par[a]);
}

int find2(int a) {
	if(!check[a]||!chi[a]) return a;
	return chi[a]=find2(chi[a]);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>N>>A>>B;
	for(int i=1;i<=N;i++) par[i]=i;
	for(int i=0;i<A;i++) {
		cin>>t1>>t2;
		chi[t1]=t2;
	}
	for(int i=0;i<B;i++) {
		cin>>t1>>t2;
		chi[t1]=t2;
		par[t2]=t1;
	}
	cin>>S;
	while(S--) {
		cin>>t1;
		t1=find2(find1(t1));
		if(check[t1]) cout<<"-1\n";
		else {
			t1=find2(find1(t1));
			check[t1]=1;
			cout<<t1<<"\n"; 
		}
	}
}