백준 2458번 - 키 순서 (C++)

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

2458번: 키 순서

 

 두 가지 방식으로 풀어낼 수 있다. 

 

1. dfs

2. 플로이드-워셜

 

1. 먼저 1번 방법을 알아보자. 내 키의 순서를 알 수 있다는 의미는 모든 노드와 연관되어 있다는 뜻이다. 더 풀어보자면 n번 노드에서 출발했을 때 모든 노드를 방문한다는 의미이다.

하지만 이 그래프는 단방향 그래프이다. 그리고 

 

작은 키 -> 큰 키 

 

로 이루어져 있다. 그러므로 두가지 dfs를 진행하는 것이 정 해이다.

 

작은키 -> 큰 키 노드를 저장한 그래프와

큰 키 -> 작은 키 노드를 저장한 그래프를 두개 선언한다. 그리고 각 노드에서 dfs를 둘 다 진행하고 방문한 노드의 갯수를 새어본다. 그리고 샌 카운트가 N - 1 개 라면 

 

즉 위의 전제인 모든 노드를 방문한다는 뜻이므로 내 키의 순서를 알 수 있다. 

시간 복잡도는 O(N^2) 이다. 

 

2. 두번째는 플로이드-워셜 방법이다. 플로이드 워셜은 양방향 그래프에서 dp를 활용해 각 정점에서 정점까지 최단거리 배열을 만들어내는 방식으로 알고있다. 그러나 플로이드 워셜은 모든 노드를 경유지로 정하는 과정을 통해 각 노드들이 이어져있는지 아닌지 확인하는 방식으로 사용할 수 있다. 

 

그러니까, 

 

문제에서 제시한 그래프

 

이 그래프를 배열로 나타내보자. 

좀 글씨가 더럽지만 ㅎ

 

여기서는 최단거리가 필요한 것이 아니다. 둘이 이어져있는가? 하는 것이 관점이다. 그러므로 0과 1로만 나타낼 수 있다. 

본래 플로이드 워셜은 

 

DP[i][j] = min(DP[i][j], DP[i][k] + DP[k][j]) 이지만 이것을 변형하여

 

if (DP[i][k] == 1 && DP[k][i] == 1) DP[i][j] = 1 

 

이것이된다. 이것을 해석하면 i, j가 k를 경유하여 이동할 수 있다면, 즉 i에서 k로 갈 수 있고, k에서 j를 갈 수 있다면 이들은 이어져 있다고 볼 수 있다. 위 배열에서 1에서 4는 갈 수 없지만 위 식을 통하면 1에서 5를 통해 4로 갈 수 있다고 표시될 것이다. 

 

그리고 이 과정을 모두 거치면

 

 

이렇게 될 것이다. 그리고 여기서 중요한 것은 i, j가 서로 이어져있는 것이 중요하다. 그러므로 dp[i][j], dp[j][i] 를 확인하여 N - 1 이면 정답 + 1을 해주면 된다. 

 

플로이드-워셜이기 때문에 시간 복잡도는 O(N^3)이지만 N이 500이므로 충분히 가능하다.

 

DFS를 진행할 때 그래프를 두개 설정하는 것이 조금 생각하기 까다로운 문제였다. 조금 더 유연하게 사고해야한다.

플로이드 워셜을 이런식으로 사용하는 것도 어려운 문제이다.

 

좋은 문제인 것 같다.

 

1번 풀이

#include <iostream>
#include <vector>

using namespace std;

vector<int> tall_node[501];
vector<int> small_node[501];
bool visited[501] = { false, };
int small_cnt = 0;
int tall_cnt = 0;

void small_dfs(int now_node) {
	visited[now_node] = true;

	for (int i = 0; i < small_node[now_node].size(); i++) {
		int next_node = small_node[now_node][i];
		if (visited[next_node] == false) {
			visited[next_node] = true;
			small_dfs(next_node);
			small_cnt++;
		}
	}
}

void tall_dfs(int now_node) {
	visited[now_node] = true;

	for (int i = 0; i < tall_node[now_node].size(); i++) {
		int next_node = tall_node[now_node][i];
		if (visited[next_node] == false) {
			tall_dfs(next_node);
			tall_cnt++;
		}
	}
}
int N, M;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int pre, after;
		cin >> pre >> after;

		tall_node[pre].push_back(after);
		small_node[after].push_back(pre);
	}

	int answer = 0;

	for (int i = 1; i <= N; i++) {
		for (int i = 0; i <= 500; i++) visited[i] = false;
		small_dfs(i);
		for (int i = 0; i <= 500; i++) visited[i] = false;
		tall_dfs(i);

		if (small_cnt + tall_cnt == N - 1) answer++;
		small_cnt = 0;
		tall_cnt = 0;
	}

	cout << answer << '\n';
}

 

2번 풀이

#include <iostream>

using namespace std;
int N, M;

int dp[501][501] = { 0, };

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

	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int s, t;
		cin >> s >> t;
		dp[s][t] = 1;
	}

	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (dp[i][k] == 1 && dp[k][j] == 1) dp[i][j] = 1;
			}
		}
	}
	int answer = 0;

	for (int i = 1; i <= N; i++) {
		int cnt = 0;
		for (int j = 1; j <= N; j++) {
			if (dp[i][j] == 1 || dp[j][i] == 1) {
				cnt++;
			}
		}

		if (cnt == N - 1) answer++;
	}

	cout << answer << '\n';
}