[ 백준 - 2458 ] 키 순서

[ 📌 서론 ]

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

 

단순히 그래프 탐색으로도 풀이가 가능할 거라고 생각은 되는게 그래프를 정, 역방향 2개 만들고 탐색 알고리즘을 수행한다면

• 정방향: 나보다 큰 키의 학생들
• 역방향: 나보다 작은 키의 학생들

선택한 노드 기준으로 다른 학생들과의 키 상하 관계를 알 수 있을 것 같지만, 나는 플로이드-워셜 알고리즘을 연습하기 위해서 알고리즘 분류에서 선택해서 문제를 골랐다.

---

[ 📌 풀이 ]

중요한점은 어떤 노드가 크고 작은지가 중요한게 아니라 도달할 수 있는지가 중점이다.

 

1. 그래프 구성하기
   • 도달 여부만 알면 되기 때문에 true/false 로 노드 관계를 구성했다.
   • 정방향은 입력으로 주어진다.
2. 플로이드-워셜 알고리즘 수행
   • 경유 노드를 거쳐서 도달할 수 있는지 체크한다.
3. 역방향 확인하기
   • 정방향 or 역방향 상관없이 모든 노드와의 관계가 형성 되었다면 해당 노드는 모든 노드와 키 순서를 갖는다.

---

[ 📌 코드 - Pypy3 ]

python 으로는 시간 초과가 나서 통과하지 못했지만... python 을 알고리즘 풀이를 위해서만 사용하다 보니 최적화할 코드가 내 눈에는 보이지 않아서 포기..

import sys
inp = sys.stdin.readline

N, M = map(int, inp().split())
graph = [[False for _ in range(N)] for _ in range(N)]
ans = 0

for _ in range(M):
  srt, end = map(int, inp().split())

  graph[srt - 1][end - 1] = True

for mid in range(N):
  for srt in range(N):
    for end in range(N):
      if graph[srt][mid] and graph[mid][end]:
        graph[srt][end] = True

for srt in range(N):
  cnt = 1

  for end in range(N):
    if graph[srt][end] or graph[end][srt]:
      cnt += 1

  if cnt == N:
    ans += 1

print(ans)

[ 📌 코드 - Java ]

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

public class Main {
    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());
        boolean[][] graph = new boolean[N][N];

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int small = Integer.parseInt(st.nextToken()) - 1;
            int tall = Integer.parseInt(st.nextToken()) - 1;

            graph[small][tall] = true;
        }

        for(int mid = 0; mid < N; mid++) {
            for(int srt = 0; srt < N; srt++) {
                for(int end = 0; end < N; end++) {
                    if(graph[mid][end] && graph[srt][mid]) {
                        graph[srt][end] = true;
                    }
                }
            }
        }

        int ans = 0;

        for(int srt = 0; srt < N; srt++) {
            int cnt = 1;
            for(int end = 0; end < N; end++) {
                if(graph[srt][end] || graph[end][srt]) {
                    cnt++;
                }
            }

            if(cnt == N) {
                ans++;
            }
        }

        System.out.println(ans);
    }
}

 

---

[ 📌 결과  ]

[ Result - Python & Java ]