[PS] 백준 2458 : 키 순서

문제

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

2458번: 키 순서

 

해설

 

이 문제를 처음 위상 정렬 문제로 생각하고 접근하였는데 단순한 위상 정렬의 개념으로는 풀 수 없는 문제 였습니다. 

 

학생의 키가 몇 번째 인지 알 수있는 학생은 어떻게 구할 수 있을까요? 단순하게 생각해서 해당 학생의 키 순서를 알기 위해서는 그 학생보다 키가 작은학생들과 큰 학생들을 모두 알아야 합니다. 

 

즉, 주어진 학생들 과의 관계를 모두 알 수있을 때 비로소 자신의 키가 몇 번째 인지 알 수 있습니다.

 

그렇다면 자기 자신과 다른 학생들의 관계를 어떻게 알 수 있을까요? 이 문제를 풀기위한 방법은 두 가지가 존재합니다.

설명상의 편의를 위해 학생을 정점으로 지칭하겠습니다.

 

1. DFS

한 정점에서 DFS를 수행했을 때 도달가능한 정점들은 자기 자신보다 큰 정점들이고, 반대로 한 정점에서 역방향으로 DFS를 수행했을 때 도달 가능한 정점들은 자기 자신보다 작은 정점들임을 알 수 있습니다. 

 

그렇게 모든 정점들에 대하여 DFS를 정방향으로 한번 역방향으로 한번 수행했을 때, 도달 가능한 정점들의 수를 세어서 더한 값이 총 정점의 개수 N + 1 이 되면 자기 자신을 제외한 모든 정점들의 관계를 알 고 있으므로 해당 정점은 몇 번째 정점인지 알 수 있습니다. 

 

 

2. Floyd-Warshall 

한 정점과 다른 정점들간의 관계를 알 수 있는 다른 방법은 물론 여러 방법이 존재하겠지만 Floyd-Warshall 알고리즘을 통해 한 정점과 모든 정점들 사이의 관계를 알 수 있습니다. 

 

한 정점에서 도달 가능한 정점, 즉 시작정점 u 로 부터 끝 정점 v 로 가는 경로가 존재한다면 u 와 v 사이의 관계를 구성할 수 있습니다. 물론 Floyd-Warshall 알고리즘을 사용하면 어느 정점이 몇번째로 크고 작은지는 알 수 없지만 인과관계를 통해 해당 정점들 사이에 관계가 존재함을 알 수 있습니다.

 

즉, 해당 정점과 관계가 있는 정점들의 개수를 기록하는 배열 A 가 있다고 가정했을 때, u 에서 v로 가는 경로가 존재한다면 A[u] += 1 그리고 A[v] += 1 과 같이 각각의 관계를 1씩 증가시켜 줄 수 있습니다.

 

이 때 관계의 개수가 총 정점의 개수 N 에서 자기 자신을 제외한 N - 1개가 되면 해당 정점은 자신을 제외한 모든 정점들 사이의 관계를 알고 있으므로 해당 정점이 몇 번째 정점인지 알 수 있습니다.

 

코드

 

DFS

import java.util.*;
import java.io.*;

/**
* 알고리즘 : Floyd-Warshall, DFS
* 1. 두 가지 방법으로 풀수 있다. 이 문제의 포인트는 모든 정점간의 관계를 확인하는 것이다.
* 2. 한 정점에서 도달할 수 있는 정점은 자신보다 큰 정점들이고
* 3. 반대로  다른 정점에서부터 자신에게 도달한 정점들은 자신보다 작은 정점들이다. 
* 4. 모든 정점에서 DFS를 역방향과 정방향 한번씩 수행하게 되면 각각의 정점에서의 관계를 구할 수 있다.
* 5. Floyd-Warshall 알고리즘을 이용한다면 모든 정점간의 관계를 구할 수 있으므로 이 방법또한 이용할 수 있다. 
* DFS를 이용한 풀이방법
*/
public class BOJ_2458_키_순서 {
	static StringBuilder sb = new StringBuilder();

	static int n, m;
	// 정방향 역방향 연결요소를 저장하기 위해 2차원 인접 리스트 생성
	static List<Integer>[][] adj;
	// 방문체크를 위한 배열 역시 정방향과 역방향 모두 고려하기 위해 2차원으로 생성
	static boolean[] visit;
	
	static int dfs(int k, int v) {
		int cnt = 1;
		visit[v] = true;
		//System.out.println(v);
		for(int nxt : adj[k][v]) {
			if(!visit[nxt]) {
				cnt += dfs(k, nxt);
			}
		}
		return cnt;
	}
	
	
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		adj = new List[2][n + 1];
		for(int i = 0; i<2; i++) {
			for(int j = 1; j<=n; j++) {
				adj[i][j] = new ArrayList<>();
			}
		}
		
		for(int i = 0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			adj[0][u].add(v);
			adj[1][v].add(u);
		}
		int ans = 0;
		for(int i = 1; i<=n; i++) {
			visit = new boolean[n + 1];
			int big = dfs(0, i);
			int less = dfs(1, i);
			if(big + less - 2 == n - 1) ans += 1;
		}
		System.out.println(ans);
	}
	
}

 

Floyd-Warshall

 

package acmicpc.gold;

import java.util.*;
import java.io.*;

/**
* 알고리즘 : Floyd-Warshall, DFS
* 1. 두 가지 방법으로 풀수 있다. 이 문제의 포인트는 모든 정점간의 관계를 확인하는 것이다.
* 2. 한 정점에서 도달할 수 있는 정점은 자신보다 큰 정점들이고
* 3. 반대로  다른 정점에서부터 자신에게 도달한 정점들은 자신보다 작은 정점들이다. 
* 4. 모든 정점에서 DFS를 역방향과 정방향 한번씩 수행하게 되면 각각의 정점에서의 관계를 구할 수 있다.
* 5. Floyd-Warshall 알고리즘을 이용한다면 모든 정점간의 관계를 구할 수 있으므로 이 방법또한 이용할 수 있다. 
* Floyd-Warshall 알고리즘을 이용한 방법
* 1. 플로이드 워셜 방법을 사용할 수 있는 이유는 다음과 같다. 
* 2. 플로이드 워셜 알고리즘을 통해 각 정점에서 다른 정점까지의 가장 짧은 거리를 구한다고 했을 때
* 3. dist[i][j] 는 정점 i에서 시작하여 정점 j까지의 최단거리를 의미한다. 이 때 dist[i][j] 가 존재하면 도달 할 수 있는 것이므로
* 4. 각각의 정점의 입장에서 살펴보면 i 보다 큰 정점이 + 1, j 보다 작은 정점이 + 1 이 되게 된다. 
* 5. 모든 거리 배열을 살펴봤을 때 각 정점에서의 합이 n - 1개가 되면 각 정점에서 모든 정점간의 관계를 알 수 있는 정점이다. 
*/
public class BOJ_2458_키_순서_2 {
	static StringBuilder sb = new StringBuilder();

	static int n, m;
	static final int inf = 501;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		int ans = 0;
		
		int[][] dist = new int[n + 1][n + 1];
		for(int i = 1; i<=n; i++) Arrays.fill(dist[i], inf);
		for(int i = 1; i<=n; i++) dist[i][i] = 0;
		
		for(int i = 0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			// 경로가 존재하면 cost 를 1로 준다. 
			dist[u][v] = Math.min(dist[u][v], 1);
		}
		
		for(int k = 1; k<=n; k++) {
			for(int i = 1; i<=n; i++) {
				for(int j = 1; j<=n; j++) {
					if(dist[i][j] > dist[i][k] + dist[k][j]) {
						dist[i][j] = dist[i][k] + dist[k][j];
					}
				}
			}
		}
		int[] path = new int[n + 1];
		for(int i = 1; i<=n; i++) {
			for(int j = 1; j<=n; j++) {
				if(i == j) continue;
				if(dist[i][j] < inf) {
					path[i] += 1;
					path[j] += 1;
					if(path[i] == n - 1) ans += 1;
					if(path[j] == n - 1) ans += 1;
				}
			}
		}
		System.out.println(ans);
	}
}