Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

BOJ-2458-키 순서 #52

Open
changicho opened this issue Jan 13, 2020 · 0 comments
Open

BOJ-2458-키 순서 #52

changicho opened this issue Jan 13, 2020 · 0 comments
Labels
clear 정답코드
Milestone

Comments

@changicho
Copy link
Owner

2458. 키 순서

링크

난이도 정답률(_%)
Gold IV 51

설계

플로이드-워셜 알고리즘

플로이드 워셜 알고리즘은 모든 정점 쌍에 대한 최단거리를 구하는 알고리즘이다.

플로이드 워셜 알고리즘을 수행하면, 모든 정점에 대한 연결 여부와 거리를 판단할 수 있다.

따라서 플로이드 워셜 알고리즘을 통해 모든 정점상의 거리를 구한다.

단방향 그래프

키 순서에 대한 그래프이므로 그래프는 단방향 그래프이다.

거리를 구한 그래프에서, [i][j]의 거리와 [j][i]거리 모두 무한인 경우가 (정점 i와 j는 절대 연결되지않으) 존재하면 이는 답이 될 수 없다.

1부터 N까지 n을 순회하고, j또한 한번 더 순회하며 [n][j]와 [j][n]이 모두 무한인지 비교하고, 모두 무한인 경우가 없는 경우 정답을 증가시킨다

정리

내 코드 빠른 코드
104 ms

고생한 점

코드

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

#define INF 1e9

using namespace std;

int graph[501][501];

void solution() {
	int N, M;
	int answer = 0;

	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			graph[i][j] = i == j ? 0 : INF;
		}
	}

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;

		graph[a][b] = 1;
	}

	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (graph[i][j] > graph[i][k] + graph[k][j]) {
					graph[i][j] = graph[i][k] + graph[k][j];
				}
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		bool canJudge = 1;

		for (int j = 1; j <= N; j++) {
			if (graph[i][j] == INF && graph[j][i] == INF) {
				canJudge = 0;
				break;
			}
		}
		if (canJudge) answer++;
	}

	cout << answer << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	solution();

	return 0;
}
@changicho changicho added the clear 정답코드 label Jan 13, 2020
@changicho changicho added this to the day6 milestone Jan 13, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
clear 정답코드
Projects
None yet
Development

No branches or pull requests

1 participant