5643. [Professional] 키 순서 - 자바(JAVA)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXQsLWKd5cDFAUo 

SW Expert Academy

 

문제 해석

1번부터 N번까지 번호가 붙어져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있습니다.

N명의 학생들의 키는 모두 다르다고 가정하겠습니다.

 

● 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명있고 자기보다 작은 학생이 3명 존재하므로 자신의 키가 몇 번째 인지 알 수 있습니다.

 

하지만 다른 학생들의 경우에는 자신의 키가 몇 번째인지 알 수 없습니다.

 

학생들의 키를 비교한 결과가 주어질 때 , 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하세요

 

문제 풀이 전 설계

학생 한명씩 돌아가면서 자신보다 큰 사람, 자신보다 작은 사람을 Count 합니다.

이를 higherCount , lowerCount라고 가정했을 때 higherCount + lowerCount = N 이 된다면 이는 자신의 키가 몇 번째인지 계산할 수 있습니다.

 

higherCount와 lowerCount를 어떻게 구할 것인가?

DFS를 통해서 탐색합니다.

 

위의 그림을 정점 하나마다 DFS탐색을 한다고 가정해보겠습니다.

 

1번부터 탐색을 시작합니다.

5 -> 2 -> 4 -> 6  정점을 탐색한 수만큼 1보다 큰 수입니다. (=4개)

 

2번을 탐색해 보겠습니다.

연결된 정점이 없으며 2보다 큰 수는 존재하지 않습니다.

 

3번은 탐색해 보겠습니다.

4 -> 2 -> 6 정점을 탐색한 수만큼 3보다 큰 수입니다. (=3개)

 

이런 식으로 heightCount는 구할 수 있습니다.

 

그러면 lowerCount는 어떻게 구해야 할까요?

 

예를 들어 4의 lowerCount를 구해보겠습니다.1번, 5번, 3번 정점이 DFS로 higherCount를 탐색하기 위해서는 필연적으로 4를 거쳐서 갑니다.그러면 이때 4가 얼마나 count 되었느냐를 기록한다면 lowerCount를 구할 수 있습니다.

 

따라서 2의 lowerCount는 1,5,3,4로 2가 됩니다.

 

코드

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

public class Solution_5643_키순서 {

    static int[] lowerCount,higherCount;
    static int result,N,M,count;
    static boolean[][] graph;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;

        graph = null;
        for (int tc = 1; tc <= T; tc++) {
            result = 0;

            N = Integer.parseInt(br.readLine());
            M = Integer.parseInt(br.readLine());

            graph = new boolean[N+1][N+1];
            lowerCount = new int[N+1];
            higherCount = new int[N+1];


            for(int i=0; i<M; i++){
                st = new StringTokenizer(br.readLine(), " ");
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                graph[from][to] = true;
            }
            //입력끝

            for(int i=1; i<=N; i++){
                visited = new boolean[N+1];
                count = 0;
                dfs(i);
                higherCount[i] = count;
            }
            for(int i=1; i<=N; i++){
                if(lowerCount[i] + higherCount[i] == N-1){
                    result++;
                }
            }

            sb.append("#" + tc + " " + result + "\n");
        }
        System.out.print(sb.toString());
    }

    private static void dfs(int currentNode) {
        for(int i=1; i<=N; i++){
            //연결되어 있지 않거나 방문된경우는 continue
            if(!graph[currentNode][i] || visited[i]){
                continue;
            }
            //방문가능하면
            visited[i] = true;
            //해당노드가 방문됬다는것은 해당 노드보다 작은노드가 1개 존재한다는 것
            lowerCount[i] += 1;
            count +=1;
            dfs(i);
        }

    }

}