[백준 / BOJ] 1613 역사

문제

출처 : www.acmicpc.net/problem/1613

1613번: 역사

n개의 사건의 개수, k개의 사건의 전후 관계, s개의 알고싶은 사건의 전후관계가 주어진다. 이때, 알고싶은 사건을 각각 A,B라 했을때 A사건이 B사건 보다 먼저 일어났으면 -1 아니라면 1 알수없다면 0을 출력하는 문제다.

 

풀이

플로이드 와샬로 풀리는 문제다. 

 

사건의 전후 관계의 개수k 가 최대 50000이므로 사건의 전후관계를 파악할때마다 매번 탐색을 해주면 시간초과가 난다.

전처리를 하며 시간초과를 피했다. 예를들어,

bool path[사건A]][사건B] 와 같은 배열이 있다고 하자.

사건 A가 사건 B보다 먼저 일어났다면, path[A][B] = true와 같이 저장해놓는다. 이때, 사건 B이후에 일어나는 사건은 모두 사건 A이후에 일어나는것 이므로 path[A][B와 연결된 노드들] = true가 된다.

이런식으로 사전에 전처리를 하면 이후에 전후관계 파악을 상수시간에 수행할수있다.

 

사전에 전후관계를 모두 파악해놓는등의 전처리를 해주며 사건의 전후관계를 상수시간에 파악하는게 중요한 문제였다. 

처음에는 플로이드 와샬을 생각하지 못하고 재귀로 전처리를 수행하다 메모리초과를 맞았다.

 

플로이드 와샬을 사용해서 모든 경로를 봐줄경우 시간복잡도는 O(N^3)이 되고, 이때, N은 최대 400 이므로 시간안에 수행할수있다.

 

(플로이드 와샬 공부좀 해야겠다..)

메모리초과 소스코드

// 메모리초과 소스코드
// xb205
// 2021.04.03
// 1613 역사
//

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n, k;
bool path[405][405];
vector<string> preCheck(405);
vector<vector<int> > history(405);

string intToString(int num){
	if(num == 0) return "";
	int _num = num / 10;
	int toString = num % 10;
	return intToString(_num) + (char)(toString + 48);
}

string preProc(int idx){
	if(preCheck[idx].size() != 0) return preCheck[idx];
	for(int i = 0; i < history[idx].size(); i++){
		preCheck[idx] += intToString(history[idx][i]) + "," + preProc(history[idx][i]);
	}
	int _idx = 0;
	for(int i = 0; i < preCheck[idx].size(); i++){
		if(preCheck[idx][i] == ','){
			if(path[idx][_idx]) {
				_idx = 0;
				continue;
			}
			path[idx][_idx] = true;
			_idx = 0;
			continue;
		}
		_idx = _idx*10 + (int)(preCheck[idx][i] - '0');
	}
	return preCheck[idx];
}

int main(){
	ios::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for(int i = 1; i <= k; i++){
		int fir, sec;
		cin >> fir >> sec;
		history[fir].push_back(sec);
		path[fir][sec] = true;
	}
	for(int i = 1; i <= n; i++){
		if(preCheck[i].length() > 0) continue;
		preProc(i);
	}
	cin >> k;
	for(int i = 1; i <= k; i++){
		int fir, sec;
		cin >> fir >> sec;
		if(path[fir][sec]) cout << -1 << "\n";
		else if(path[sec][fir]) cout << 1 << "\n";
		else cout << 0 << "\n";
	}
	return 0;
}

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1613%20%EC%97%AD%EC%82%AC/main.cpp

devxb/JJUNalgo