[BOJ] 백준 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인 학생보다 키가 작은 것을 의미한다. 

 

 

출력

자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다. 

 

 

풀이

플로이드 와샬 알고리즘을 활용한 문제였습니다. 11403번 경로찾기 문제를 응용하여 풀 수 있었습니다.

이 문제에 관심이 있으신 분은 아래 포스팅을 참조하시길 바랍니다.

 

 

[BOJ] 백준 11403번 : 경로 찾기 (JAVA)

 

 

문제에서의 핵심은 특정 학생보다 키가 큰 사람과 작은 사람을 명확하게 가려낼 수 있는지 여부였습니다.

따라서, 자신을 제외한 모든 정점에서 모든 정점에 대하여 이동할 수 있는지 파악해야 합니다.

 

전반적인 로직은 아래와 같습니다.

 

 

1. 문제의 입력을 받은 배열에 대하여 플로이드 와샬 알고리즘을 취한다.

2. 문제의 입력과 반대로 받은 배열에 대하여 플로이드 와샬 알고리즘을 취한다.

3. 1번과 2번의 배열 or 연산한다.

4. or 연산한 배열에서 자신은 제외한 학생 모두를 탐색할 수 있는 인덱스의 개수를 계산한다.

 

 

여기서 문제의 입력과 반대로 받았다는 의미는 "1 5"대신 "5 1"로 키 순서를 반대로 입력받았다는 뜻입니다.

 

이제, 2번과 3번 과정을 하게된 이유를 설명드리겠습니다.

 

1차적으로 문제의 입력이 주어진 대로 플로이드 와샬 알고리즘을 전개를 하면, 문제가 하나 발생합니다.

 

문제의 입력을 예시로 들면, 4번 학생의 경우 2번과 6번 학생 쪽으로만 화살표가 있기때문에 나머지 1, 3, 5에 대해서는 이동을 할 수가 없습니다.

 

하지만, 그래프 상으로는 1, 3, 5가 명확하게 4번보다 키가 작기때문에 이에 대해서도 판단해야 합니다.

 

저는 여기서 문제의 입력과 반대로 입력받은 새로운 배열을 정의하여 마찬가지로 플로이드 와샬 알고리즘을 전개하였습니다. 이 경우, 4번 학생이 이동할 수 있는 화살표는 1, 3, 5번 학생입니다.

 

그리고 두 배열을 or 연산을 하면, 4번 학생이 갈 수 있는 길은 1, 2, 3, 5, 6으로 모든 학생에 대하여 이동할 수 있습니다. 결과적으로 4번 학생은 자신의 키가 몇 번째로 큰 지 파악할 수 있게 되는 것입니다.

 

4번 학생이 아니라 5번 학생을 기준으로 해 봅시다.

문제의 입력을 그대로 받은 배열에 대해서 플로이드 와샬 알고리즘을 취하면, 5번 학생은 2, 4, 6번 학생을 탐색할 수 있습니다.

 

문제의 입력을 반대로 받은 배열에 대해서 플로이드 와샬 알고리즘을 취하면, 5번 학생은 1번 학생만 탐색할 수 있습니다.

 

위 두 배열을 or 연산하면 1, 2, 4, 6번으로 3번 학생에 대해서는 키 비교를 할 수 없다는 사실을 알 수 있습니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
 
        // 문제에서 주어진대로 입력을 받음.
        boolean[][] arr = new boolean[N + 1][N + 1];
 
        // 문제에서 주어진 것과 반대로 입력을 받음.
        boolean[][] reverse_arr = new boolean[N + 1][N + 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());
 
            arr[a][b] = true;
            reverse_arr[b][a] = true;
        }
 
        // 플로이드 와샬 알고리즘 수행
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (arr[i][k] && arr[k][j]) {
                        arr[i][j] = true;
                    }
                }
            }
        }
 
        // 플로이드 와샬 알고리즘 수행
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (reverse_arr[i][k] && reverse_arr[k][j]) {
                        reverse_arr[i][j] = true;
                    }
                }
            }
        }
 
        // 특정 학생에 대하여 키가 큰 사람과 작은 학생 모두를 파악 가능.
        // 만약 |을 취한 값이 false라면, 그 학생과 키 비교를 할 수 없다는 의미.
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                arr[i][j] |= reverse_arr[i][j];
            }
        }
 
        int ans = 0;
        outer: for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) { // 자기 자신은 제외.
                    continue;
                }
 
                // 키 비교를 할 수 없는 학생이 존재한다면 continue.
                if (!arr[i][j]) {
                    continue outer;
                }
            }
            ans++;
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.