[BOJ] 백준 1325. 효율적인 해킹 (Silver I)

스터디그룹 채점현황 둘러보다가 발견한 문제.

결론부터 까고 말하자면, 이 문제는 BFS/DFS 뿐만 아니라 SCC로도 풀 수 있고, 만약 이게 정해라면 Platinum IV 티어 정도 받았을 것 같다.

 

문제 풀기 전에는 티어 열람 기능을 꺼놓기 때문에, 처음 봤을 땐 되게 쉬울줄 알았던 문제인데, 막상 풀 땐 그렇지 않았던 문제이다. 시간제한이 5초나 돼서 단순한 방법으로 풀리지만, 꽤 배울 점이 많은 문제.

문제는 아래와 같다.

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

1325번: 효율적인 해킹

---

의식의 흐름 및 해설

단순 브루트포스 + DFS/BFS 로는 O(N*(N+M))이라서 약 11억번, 실제로는 그 이상의 연산횟수가 들기 때문에 통과하지 못할 것이라 생각했다. (실제로는 통과함.)

 

그래서 처음에는 차수가 제일 작은 노드에서부터 탐색을 시작해서 노드들의 차수를 갱신하는 방식으로 탐색 횟수를 줄이려 하였다. (리프 노드만 확인하면 안되는 것이, 리프 노드끼리도 차수가 달라 답이 달라질 수 있다.)

 

그런데, 이럴 경우 cycle이 존재할 때, 시간초과/메모리초과 현상을 겪는다.

어떻게 할까 고민하다가, 일단 아싸리 모르겠다 하고 시간 제한이 5초라 O(N*(N+M))의 브루트포스 + BFS로 전체를 탐색하는 코드를 질러보았다.

1초에 2~3억번 연산이 가능하기 때문에 아슬아슬하게 통과되겠다 했는데 정말로 통과되었다. 나의 경우 2608ms로 통과했다.

 

시간을 더 줄이는 방법?

다른 분들의 코드도 3000~4000ms의 코드들이 많았기 때문에 이게 정석 풀이구나~ 하고 넘어가려는 순간,

500~1500ms의 코드들이 눈에 띄기 시작했다.

알고보니 SCC로 미리 사이클들을 만들어놓고, 그 SCC끼리 BFS/DFS를 돌리면 시간을 더 줄일 수 있었다.

이게 왜 시간이 줄어드냐면, 어차피 시간복잡도는 O(NM)이긴 하지만, 일부 SCC들을 미리 DFS를 돌리기 때문에 O(N/2 * M/2) 가 O(NM / 4) 인 것처럼, meet in the middle 효과를 내는 것이다!

 

따라서 SCC들을 O(M)에 만들어주고, SCC끼리 dfs를 돌려 O(NM)이지만,

훨씬 상수가 작은 O(NM)의 시간복잡도로 더 빠른 코드를 완성할 수 있다.

 

그리고 이 문제는 어차피 전체탐색을 해야되기 때문에 dfs나 bfs나 시간이 거의 유사한 듯하다.

---

코드(2608ms)

시간초과를 겪을까봐 BFS를 이용하였다.

지금 생각해보면 어차피 이 문제에선 BFS도 DFS와 마찬가지로 전체탐색을 해야되므로 DFS와 비슷한 시간으로 나올 것 같다.

 

**휴대폰으로 풀었기 때문에 VS에서의 컨벤션이 지켜지지 않아 가독성이 떨어진다.**

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
vector<int> v[10003];
int n,m,in[10003];
bool vis[10003];
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m;
	while(m--){
		int a,b;
		cin>>a>>b;
		v[b].push_back(a);
	}
	int M=0;
	for(int j=1;j<=n;j++){
		queue<int> q;
		fill(vis,vis+10003,false);
		vis[j]=true;
		int k=1;
		q.push(j);
	    while(!q.empty()){
		    int x=q.front();
	    	q.pop();
	    	for(int i:v[x]){
		    	if(vis[i])continue;
		    	vis[i]=true;
		    	k++;
		     	q.push(i);
		    }
	    }
	    in[j]=k;
	    M=max(M,k);
	}
	for(int i=1;i<=n;i++){
		if(in[i]==M)cout<<i<<" ";
	}
}

---

코드(756ms)

SCC를 이용한 solution

 

**휴대폰으로 풀었기 때문에 VS에서의 컨벤션이 지켜지지 않아 가독성이 떨어진다.**

#include <bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define press(v) v.erase(unique(all(v)),v.end())
using namespace std;
const int MAX=10003;
int n,m,id,sccnum[MAX],d[MAX],sz[MAX];
vector<int> v[MAX],c[MAX];
vector<vector<int>> scc;
bool vis[MAX];
stack<int> st;
// scc 만들기
int dfs(int x){
	d[x]=++id;
	int ret=d[x];
	st.push(x);
	for(int i:v[x]){
		if(!d[i])ret=min(ret,dfs(i));
		else if(sccnum[i]==-1)ret=min(ret,d[i]);
	}
	if(ret==d[x]){
		vector<int> tmp;
		while(1){
			int t=st.top();
			st.pop();
			sccnum[t]=scc.size();
			sz[sccnum[t]]++;
			tmp.push_back(t);
			if(t==x)break;
		}
		scc.push_back(tmp);
	}
	return ret;
}
// scc끼리 dfs
int solve(int cur){
	int ret=sz[cur];
	vis[cur]=true;
	for(int i:c[cur]){
		if(vis[i])continue;
		ret+=solve(i);
	}
	return ret;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m;
	while(m--){
		int a,b;
		cin>>a>>b;
		v[b].push_back(a);
	}
    // scc Number를 0-index로 시작해서 초기화는 -1로 함.
	fill(sccnum,sccnum+MAX,-1);
	for(int i=1;i<=n;i++){
		if(!d[i])dfs(i);
	}
    // scc끼리 인접리스트 생성
	for(int i=1;i<=n;i++){
		for(int j:v[i]){
			if(sccnum[i]==sccnum[j])continue;
			c[sccnum[i]].push_back(sccnum[j]);
		}
	}
	for(int i=0;i<scc.size();i++){
		sort(all(scc[i]));
		press(scc[i]);
	}
    // scc끼리 dfs로 갈 수 있는 원소 수 확인
	int M=0;
	vector<int> sccres,res;
	for(int i=0;i<scc.size();i++){
		fill(vis,vis+MAX,false);
		int ret=solve(i);
		if(M<ret){
			M=ret;
			sccres.clear();
			sccres.push_back(i);
		}
		else if(M==ret){
			sccres.push_back(i);
		}
	}
	for(int i:sccres){
		for(int j:scc[i]){
			res.push_back(j);
		}
	}
	sort(all(res));
	for(int i:res)cout<<i<<" ";
}

---

시간초과...메모리초과... 틀렸습니다... 맞았습니다... 무려 4가지 결과나 존재한다.

백준 잔디 채우기용으로 풀려다가,

오히려 SCC 복습까지 돼버린 문제.

 

요즘 한창 페어프로그래밍으로 구현 마감일 때문에 바빠서 백준 못하다가,

오히려 덕분에 새벽에 scc 복습도 하게 만들어줘서 뿌듯했던 문제였다.