백준 Baekjoon 1613 역사 풀이

사용언어

Visual studio 2019 C++

생각하기

플로이드 워샬 알고리즘 사용 DFS로는 시간초과가 남

XX DFS로 푼 시간초과 풀이 XX

입력값을 넣었을때 내코드에서는 정답은 나왔지만 백준에 넣었을 때엔 시간초과라는 문제 발생

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
vector<int> v[400];
bool visited[400];

void dfs(int a) {
	visited[a] = true;

	for (int i = 0; i < v[a].size(); i++) {
		if (!visited[v[a][i]]) {
			dfs(v[a][i]);
		}
	}
}

int main() {
	int n, k;
	cin >> n >> k; // 사건, 관계

	for (int i = 0; i < k; i++) {
		int a, b; cin >> a >> b;
		v[a].push_back(b);
	}

	int s; cin >> s;
	for (int i = 0; i < s; i++) {
		int a, b; cin >> a >> b;
		memset(visited, 0, sizeof(visited));
		dfs(a);
		if (!visited[b]) {
			memset(visited, 0, sizeof(visited));
			dfs(b);
			if (visited[a])
				cout << 1 << "\n";
			else
				cout << 0 << "\n";
		}
		else
			cout << -1 << "\n";
	}
}

플로이드 워샬 알고리즘

모든 정점들 사이의 최단경로를 구하는 알고리즘.

플로이드 워샬 알고리즘의 동작방식

for (int k = 1; k <= N; k++) {         // 중간점{
	for (int i = 1; i <= N; i++) {   // 시작점
		for (int j = 1; j <= N; j++) { // 도착점
			if (시작점과 도착점의 관계를 알고싶으면) {
				if (시작점 > 중간점 && 중간점 > 도착점) 
					시작점 > 도착점
				else if (시작점 < 중간점 && 중간점 < 도착점) 
					시작점 < 도착점
			}
		}
	}
}

문제에 대입해보면

for (int k = 1; k <= N; k++) { // 중간점
	for (int i = 1; i <= N; i++) { // 시작점
		for (int j = 1; j <= N; j++) { // 도착점
			if (MAP[i][j] == 0) {
				if (MAP[i][k] == 1 && MAP[k][j] == 1)
					MAP[i][j] = 1;
				else if (MAP[i][k] == -1 && MAP[k][j] == -1)
					MAP[i][j] = -1;
			}
		}
	}
}

[1613 맞은 풀이]

#include<iostream>
#include<vector>
#define endl "\n"
#define MAX 401
using namespace std;
int N, K, S;
int MAP[MAX][MAX];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> K;
	for (int i = 0; i < K; i++) {
		int a, b;
		cin >> a >> b;
		MAP[a][b] = -1;
		MAP[b][a] = 1;
	}
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (MAP[i][j] == 0) {
					if (MAP[i][k] == 1 && MAP[k][j] == 1) {
						MAP[i][j] = 1;
					}
					else if (MAP[i][k] == -1 && MAP[k][j] == -1) {
						MAP[i][j] = -1;
					}
				}
			}
		}
	}

	cin >> S;
	for (int i = 0; i < S; i++) {
		int a, b;
		cin >> a >> b;
		cout << MAP[a][b] << endl;
	}
}

참고풀이: https://yabmoons.tistory.com/107