Skip to content

BOJ-2458-키 순서 #52

Open
Open

Description

@changicho

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;
}

Activity

  1. added this to the day6 milestone on Jan 13, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    clear정답코드

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions