풀이를 간략하게 설명하자면 먼저사람들을 정점으로 간주한다. 모든 정점간의 거리를 INF 로 초기화 해주고주어진 연결관계를 이어주고, 플로이드 워셜을 통해 특정 사람이 모든 사람과의 거리를 체크해서 값을 갱신해준다.
2중 for문을 통해서 사람과 사람간의 거리가 하나라도 INF 수를 확인하면 된다. 자세한 풀이는 밑에서 설명하겠다.
🧩 프로세스
📚 초기화 및 선언
: 위에서 설명한대로 모든 정점을 INF = 987654321 로 초기화 해주고, 주어진 관계는 거리를 1로 입력해준다.
public static void input() throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// 모든 정점 초기화
dist = new int[N+1][N+1];
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
dist[i][j] = INF;
}
}
// 학생의 키 순서를 아는 경우 1로 거리 배열 입력
for(int i=1; i<=M; i++) {
st = new StringTokenizer(br.readLine());
A = Integer.parseInt(st.nextToken());
B = Integer.parseInt(st.nextToken());
dist[A][B] = 1;
}
}
📚 플로이드 워셜
: 특정 학생이 모든 학새오가의 거리를 체크하기 위해 플로이드 워셜을 진행한다.
// 특정 학생이 모든 학생과의 거리를 체크해야 하므로 플로이드 워셜 수행
for(int k=1; k<=N; k++) {
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
dist[i][j] = Math.min(dist[i][k] + dist[k][j], dist[i][j]);
}
}
}
플로이드 워셜을 통해 최단거리를 갱신했으면 2중 for문을 통해 두 정점을 비교한다. 두 정점 중 하나라도 INF 이 아닌 값이 있다면 이것은 비교할 수 있다는 의미이다. 한 정점에서 나머지 정점까지 의 거리가 INF이 아닌 수를 카운트하고, 그 수가 N-1 과 같다면 이는 해당 학생의 키 순서를 알 수 있다.
/*
* 모든 학생과의 비교가 가능한 경우
* => 거리가 INF가 아닌 학생의 수가 N-1인 경우 : 키가 몇번째인지 알 수 있음!
*/
ANS = 0;
for(int i=1; i<=N; i++) {
int CNT = 0;
for(int j=1; j<=N; j++) {
if(dist[i][j] != INF || dist[j][i] != INF) CNT++;
}
if(CNT == N-1) ANS++;
}
✅ 전체 코드
: 플로이드 워셜을 좀 풀어서 적용하기 쉬울 줄 알았는데 다양한 풀이가 있고 아직 많이 부족함을 느낄 수 있었던 문제였다.
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N,M,A,B,ANS;
static int[][] dist;
static final int INF = 987654321;
public static void main(String[] args) throws IOException {
input();
process();
}
public static void input() throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// 모든 정점 초기화
dist = new int[N+1][N+1];
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
dist[i][j] = INF;
}
}
// 학생의 키 순서를 아는 경우 1로 거리 배열 입력
for(int i=1; i<=M; i++) {
st = new StringTokenizer(br.readLine());
A = Integer.parseInt(st.nextToken());
B = Integer.parseInt(st.nextToken());
dist[A][B] = 1;
}
}
public static void process() {
// 특정 학생이 모든 학생과의 거리를 체크해야 하므로 플로이드 워셜 수행
for(int k=1; k<=N; k++) {
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
dist[i][j] = Math.min(dist[i][k] + dist[k][j], dist[i][j]);
}
}
}
/*
* 모든 학생과의 비교가 가능한 경우
* => 거리가 INF가 아닌 학생의 수가 N-1인 경우 : 키가 몇번째인지 알 수 있음!
*/
ANS = 0;
for(int i=1; i<=N; i++) {
int CNT = 0;
for(int j=1; j<=N; j++) {
if(dist[i][j] != INF || dist[j][i] != INF) CNT++;
}
if(CNT == N-1) ANS++;
}
System.out.println(ANS);
}
}