BOJ 2458 키 순서
- 그래프
- Floyd-Warshall
- Gold 4
🔍 문제 설명
https://www.acmicpc.net/problem/2458
1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.
1번 학생의 키 < 5번 학생의 키
3번 학생의 키 < 4번 학생의 키
5번 학생의 키 < 4번 학생의 키
4번 학생의 키 < 2번 학생의 키
4번 학생의 키 < 6번 학생의 키
5번 학생의 키 < 2번 학생의 키
이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다.
1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다. 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다.
학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.
✔ 입력
첫째 줄에 학생들의 수 N (2 ≤ N ≤ 500)과 두 학생 키를 비교한 횟수 M (0 ≤ M ≤ N(N-1)/2)이 주어진다. 다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 두 양의 정수 a와 b가 주어진다. 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다.
✔ 출력
자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다.
💡 풀이 1. Floyd-Warshall
키 순서를 알려면 모든 학생에 대해서 키가 작거나, 키가 큰지 알 수 있어야 한다.
이는 즉 비교하고자 하는 학생(idx)는 모든 학생과 연결이 되어있어야 한다.
idx와 이어지지 않은 노드가 하나라도 있으면 키 순서를 알 수 없다.
따라서 모든 정점간의 관계를 알 수 있는 플로이드 워셜(Floyd-Warshall) 알고리즘을 이용한다.
연결되어 있다면 minEdge를 1로 표시했고,
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine(), " ");
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
minEdge[A][B] = 1;
}플로이드 워셜로 각 정점사이의 거리를 모두 구했다.
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
if(k==i) continue;
for (int j = 1; j <= N; j++) {
if(i == j || k == j) continue;
minEdge[i][j] = Math.min(minEdge[i][j], minEdge[i][k] + minEdge[k][j]);
}
}
}그리고 모든 사람과 연결되어 있는지 확인해보면 된다.
💡 풀이 1. 소스코드 (Floyd-Warshall)
package boj.graph;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main_BJ_2458_키순서_플로이드와샬 {
static int[][] minEdge;
static int N, M, answer;
static int INF = 100000;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
minEdge = new int[N+1][N+1];
for (int i = 0; i <= N; i++) {
Arrays.fill(minEdge[i], INF);
}
// 입력처리 : 키 순서를 안다면 1 저장
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine(), " ");
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
minEdge[A][B] = 1;
}
// 플로이드 와샬 : 경유지 - 출발지 - 도착지 3중 for문
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
if(k==i) continue;
for (int j = 1; j <= N; j++) {
if(i == j || k == j) continue;
minEdge[i][j] = Math.min(minEdge[i][j], minEdge[i][k] + minEdge[k][j]);
}
}
}
// 키를 알 수 있느 ㄴ경우.
// INF가 아니고 cnt가 N-1
for (int i = 1; i <= N; i++) {
int cnt = 0;
for (int j = 1; j <= N; j++) {
if(i==j) continue;
if(minEdge[i][j]==INF && minEdge[j][i]==INF) break;
cnt++;
}
if(cnt==N-1) answer++;
}
System.out.println(answer);
}
}
💡 풀이 2. BFS
int answer : 정확하게 키 순서를 알 수 있는 학생 수
ArrayList<Integer>[] winList : 1~n번 학생이 키로 이기는 학생 리스트
ArrayList<Integer>[] loseList : 1~n번 학생이 키로 지는 학생 리스트
int getWinCnt(int idx,int n) : idx 학생이 키로 이긴 학생의 수를 구하는 bfs 메소드
int getLoseCnt(int idx,int n) : idx 학생이 키로 지는 학생의 수를 구하는 bfs 메소드
BFS로 풀었다.
이 문제에서 구해야 하는 것은 정확하게 키 순서를 매길 수 있는 학생의 수 입니다.
i번 학생의 키 순서를 구하려면, 모든 학생에 대해 i번 학생이 큰지 작은지 알 수 있어야 합니다. 이는 i번 선수가 n-1번의 비교를 해야 한다는 뜻입니다.
즉 n명의 학생가 있을 때, i번 학생의 winCnt(이긴 횟수), loseCnt(진 횟수)의 합이 n-1이어야 합니다
키 순서를 비교한 결과를 winList, loseList에 먼저 저장하고,
for문으로 idx=1부터 idx=n번 학생에 대해 winCnt와 loseCnt를 구했습니다.
각각의 cnt는 bfs와 위에서 구한 winList, loseList를 이용하여 구할 수 있었습니다.
구한 winCnt+loseCnt의 합이 n-1이라면 answer를 하나 증가시킵니다.
💡 풀이 2. 소스코드 (BFS)
package boj.graph;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main_BJ_2458_키순서_BFS {
static ArrayList<Integer>[] winList, loseList;
static int N, M, answer;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
winList = new ArrayList[N+1]; //1~n번 학생이 이긴 선수 리스트
loseList = new ArrayList[N+1]; //1~n번 학생이 진 선수 리스트
for (int i = 0; i <= N; i++) {
winList[i] = new ArrayList<>();
loseList[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine(), " ");
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
winList[A].add(B); //A가 B보다 크다.
loseList[B].add(A); //B가 A보다 작다.
}
for (int idx = 1; idx <= N; idx++) {
int winCnt = getWinCnt(idx, N);
int loseCnt = getLoseCnt(idx, N);
if(winCnt + loseCnt == N-1) answer++;
//큰 학생 + 작은 학생 = n-1이면 모든 키 비교의 결과를 알수 있으므로 순서를 구할 수 있다.
}
System.out.println(answer);
}
private static int getWinCnt(int idx,int n) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[n+1];
int winCnt = 0;
queue.add(idx);
visited[idx]=true;
while(!queue.isEmpty()) {
int playerNum = queue.poll();
for (int i = 0; i < winList[playerNum].size(); i++) {
int tgtNum = winList[playerNum].get(i);
if(visited[tgtNum]) continue;
visited[tgtNum] = true;
queue.add(tgtNum);
winCnt++;
}
}
return winCnt;
}
private static int getLoseCnt(int idx,int n) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[n+1];
int loseCnt = 0;
queue.add(idx);
visited[idx]=true;
while(!queue.isEmpty()) {
int playerNum = queue.poll();
for (int i = 0; i < loseList[playerNum].size(); i++) {
int tgtNum = loseList[playerNum].get(i);
if(visited[tgtNum]) continue;
visited[tgtNum] = true;
queue.add(tgtNum);
loseCnt++;
}
}
return loseCnt;
}
}
