99클럽 코테 스터디 6일차 - 백준, 키 순서

문제 풀이 예상 시간보다 지나가면 다른 해석을 보고 있습니다. 

문제

풀이

문제 해석

1. 인원수와 그 인원 수 간의 일부 키 관계가 주어진다. 

2. 주어진 관계만으로 내가 몇 번째인지 알 수 있는 번호는 몇 개인지 출력해라.

문제 풀이

1. 나와 모든 인원의 관계를 명확히 알아야 내가 몇번째 인지 알 수 있다.

2. 모든 인원과의 관계를 알기 위해서는 나와 직간접적으로 닿아있어야 한다.

3. 나보다 작은 사람보다 작은 사람은 나보다 작다. 반대도 마찬가지

4. 해서 나보다 작은 사람과 그사람보다 큰 사람인 경우에 그 사람과의 관계를 저장한다.

소스코드

package online.judge.baekjoon;

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

/**
 * 키 순서
 * 골드 4
 * 플로이드 워샬
 */
public class No2458 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());


        //학생 수와 비교 횟수
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        //학생 간 관계를 나타 낼 배열
        int[][] tallCom = new int[n][n];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;

            tallCom[a][b] = 1;
            tallCom[b][a] = 2;
        }

        //비교해서 작은거는 1로 큰거는 2로
        for (int i = 0; i < n; i++) {// 중간 비교
            for (int j = 0; j < n; j++) {//앞
                for (int k = 0; k < n; k++) {//뒤
                    if(tallCom[j][i] == 1 && tallCom[i][k] == 1){
                        tallCom[j][k] = 1;
                        tallCom[k][j] = 2;
                    }
                }
            }
        }

        //관계가 명확하지 않으면(본인을 제외한 0이 또 있다면 안됨) 넘어감
        int answer = 0;
        for (int i = 0; i < n; i++) {
            boolean flag = true;
            for (int j = 0; j < n; j++) {
                if(i == j) continue;
                if(tallCom[i][j] == 0) {
                    flag = false;
                    break;
                }
            }
            if(flag) answer++;
        }
        System.out.println(answer);
    }

}

 

TIL

• 풀이 해봤던 문제라 쉽게 다시 풀었다