[백준 / Java] 2458번: 키 순서 (골드4)

문제 풀이 날짜: 2023.10.04
포스트 작성일: 2023.10.04

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 2458번: 키 순서 (골드4)

 

키워드

최단 경로, 플로이드-워샬

 

풀이 접근법

• 자신의 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 알 수 있는 경우 ⇒ 위상 정렬이라고 생각하기 쉬우나, 위상 순서가 확실히 결정되는 것(큐의 크기가 1)으로는 문제에서 요구하는 답을 얻을 수 없다.
• 예제 테케의 경우, 4번 노드만이 다른 모든 노드와 직·간접적으로 연결되어 있다. 이 경우만 가능한 경우로 센다.
  • 직·간접적으로 연결 ⇒ 한 노드로부터 다른 모든 노드로 가는 INF가 아닌 경로가 존재한다. ⇒ 플로이드-워샬
  • 이러한 노드의 개수를 세면 답이 된다.
• 이를 구하기 위해 그래프에서 역방향 연결 여부까지 확인해야 한다. 그래프를 생성할 때 역방향까지 연결해야 하는 것은 아니고, 어떤 노드 i에서 j까지 가는 경로 또는 j에서 i로 가는 경로가 존재하는 지를 조사한다.
• 시간을 절약하기 위해서 거리를 구하지 않고 연결 여부만 boolean 배열로 체크해도 답이 나온다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	private static boolean[][] D;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] temp = br.readLine().split(" ");
		
		int N = Integer.parseInt(temp[0]);
		int M = Integer.parseInt(temp[1]);
		
		D = new boolean[N][N];

		for(int i = 0; i < M; i++) {
			temp = br.readLine().split(" ");
			
			int u = Integer.parseInt(temp[0]) - 1;
			int v = Integer.parseInt(temp[1]) - 1;
			
			D[u][v] = true;
		}
		
		for(int k = 0; k < N; k++) { //경유지
			for(int i = 0; i < N; i++) { //출발지
				for(int j = 0; j < N; j++) { //도착지
					if(D[i][k] && D[k][j]) { //간접 경로가 존재한다면
						D[i][j] = true; //i, j가 연결된 것으로 본다.
					}
				}
			}
		}
		
		int[] counts = new int[N];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(D[i][j] || D[j][i]) { //양방향 중 한 쪽으로 연결되어 있다면
					counts[i]++;
				}
			}
		}
		
		int result = 0; //다른 모든 점들과 연결된 노드의 수
		for(int n : counts) {
			if(n == N - 1) result++;
		}
		
		System.out.print(result);
	}

}

---

 

 

참고한 링크

https://loosie.tistory.com/503