[백준 알고리즘]2458번: 키 순서_Java

[문제]

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	6 6 1 5 3 4 5 4 4 2 4 6 5 2	1
2	6 7 1 3 1 5 3 4 5 4 4 2 4 6 5 2	2
3	6 3 1 2 2 3 4 5	0

 

---

>문제 풀이

1~N번 까지의 학생들의 키 순서를 상대적으로 비교한 정보가 주어진다.

이 정보를 통해 몇 번째로 키가 큰지 알 수 있는 학생이 몇 명인지 출력하라

​

어떤 학생에 대하여 자신을 제외한 1~N까지의 학생과 키를 비교할 수 있는지 확인해야한다.

그러나 한 명씩 매번 연산을 한다면 시간초과가 발생한다.

>> 모든 경로를 구해놓고서 1~N까지의 학생들이 가능한지 안한지만 체크해야한다.

​

플로이드-워셜 알고리즘

: 음의 간선 or 양의 간선에서 최단거리 파악할 수 있음

: 음의 싸이클 있으면 안되고 N<500일 때 다익스트라 보다 효율이 좋다고 알고있다.

​

​

::구현::

​

1) (N과 M을 입력받고,) int[][] distance 배열 선언 후 INF=999999999로 초기화

연결 여부 확인 할 때 비정상값인 경우 거르기 위해서 INF로 초기화 해놓는 것이다.

​

2) 키 정보값을 입력 받는다.

ex) i번 학생 < j번 학생 인 경우 distance[i][j]= 1;

​

3) for문을 돌면서 distance[i][j] 와 distance[i][k]+distance[k][j] 중 최소값을 선택한다.

( i는 출발지, j는 목적지, k는 경유지 // distance[i][j]: i에서 j로 가는 거리 )

어느 한쪽이 INF이면 다른 쪽을 선택할 것이고, 둘 다 INF이면 4)번에서 걸러진다.

​

4) 2중 for문 :: 1~N까지 확인하면서 distance[i][j]나 distance[j][i]가 INF가 아닌 경우를 cnt++카운팅 해서

cnt==N-1인 경우 answer++ 카운팅

//자기 자신 distance[i][j]는 무조건 INF 이다.

//그러니까 자신을 뺀 나머지랑 연결되어 있어야 하는데 이것을 cnt= N-1을 체크해줌으로써 확인이 가능하다.

 

>전체 코드

큰 차이는 없지만 두 가지 방법으로 풀어보았다.

어차피 연결여부만 확인하면 된다는 부분에서, int 보다는 boolean이 더 목적에 맞을 것 같아서 2)번으로도 고쳐본 것이다. 위의 설명을 이해했다면 2)번은 int->boolean이기 때문에 코드만 봐도 이해가 될 것 이다.

​

1) int[][] 배열 이용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException{
		final int INF= 999999999;
		int N, M, answer=0;
		int a, b;
		int[][] distance;
		
		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());
		
		distance= new int[N+1][N+1];
		for(int i=1; i<N+1; i++) {
			Arrays.fill(distance[i], INF);
		}
		
		for(int i=0; i<M; i++) {
			st= new StringTokenizer(br.readLine());
			
			a= Integer.parseInt(st.nextToken());
			b= Integer.parseInt(st.nextToken());
			
			distance[a][b]= 1; //a, b가 서로 연결되어있다.
		}
		
		//플로이드-워셜: 경유지-출발지-도착지 : 3중 for문
		//출발 i, 도착:j, 경유지:k
		for(int k=1; k<=N; k++) {
			for(int i=1; i<=N; i++) {
				for(int j=1; j<=N; j++) {
					distance[i][j]= distance[i][j]<=distance[i][k]+distance[k][j]?
									distance[i][j]:distance[i][k]+distance[k][j];
				}
			}
		}
		
		for(int i=1; i<=N; i++) {
			int cnt=0;
			for(int j=1; j<=N; j++) {
				if(distance[i][j]!=INF || distance[j][i]!=INF) cnt++;
			}
			if(cnt==N-1) answer++;
		}
		
        System.out.println(answer);
	}//main
        
}

2) boolean 배열

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException{
		int N, M, answer=0;
		int a, b;
		boolean[][] distance;
		
		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());
		
		distance= new boolean[N+1][N+1];
		
		for(int i=0; i<M; i++) {
			st= new StringTokenizer(br.readLine());
			
			a= Integer.parseInt(st.nextToken());
			b= Integer.parseInt(st.nextToken());
			
			distance[a][b]= true; //a, b가 서로 연결되어있다.
		}
		
		//플로이드-워셜: 경유지-출발지-도착지 : 3중 for문
		//출발 i, 도착:j, 경유지:k
		for(int k=1; k<=N; k++) {
			for(int i=1; i<=N; i++) {
				for(int j=1; j<=N; j++) {
					if(distance[i][k]&&distance[k][j]) {
						distance[i][j]= true;
					}
				}
			}
		}
		
		boolean check;
		for(int i=1; i<=N; i++) {
			check= false;
			for(int j=1; j<=N; j++) {
				//i에서 시작해서 연결이 안된 학생이 있다.
				if(i!=j && !distance[i][j] && !distance[j][i]) {
					check= true;
					break;
				}
			}
			if(!check) answer++;
		}
		
        System.out.println(answer);
	}//main
        
}

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

2458번: 키 순서