백준 2458 키 순서

키 순서

문제는 백준에서 확인 할 수 있다.

✔ 접근방법

1. 자신의 키 순서를 정확하게 알기 위해서는 아래의 조건을 만족해야 한다.
   조건 : 자신을 제외한 모든 노드와의 연관관계가 있어야 한다.
2. 플로이드워셜 알고리즘을 이용
3. 자신을 제외한 모든 노드와의 연관관계를 확인한다.
4. 조건에 맞는 노드의 수를 세어준다.

✔ 코드

import sys

if __name__ == "__main__":
    answer = 0
    N, M = map(int, input().split())

    adj = [[0]*N for _ in range(N)]
    for i in range(N):
        adj[i][i] = 0
    
    for _ in range(M):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        adj[a-1][b-1] = 1

    # for line in adj:
    #     print(line)
    
    for mid in range(N):
        for i in range(N):
            for j in range(N):
                # adj[i][j] = min([adj[i][j], adj[i][mid]+adj[mid][j]])
                if adj[i][mid] == 1 and adj[mid][j] == 1:
                    adj[i][j] = 1

    # for line in adj:
    #     print(line)

    for i in range(N):
        flag = True
        for j in range(N):
            if i != j and \
                adj[i][j] == 0 and \
                adj[j][i] == 0:
                flag = False
        
        if flag:
            answer += 1

    print(answer)

☝ 팁

• 백준 내의 python3 컴파일러로 답안을 제출하면 시간초과가 발생한다.
  pypy 컴파일러로 답안을 제출하면 해결된다.
• 플로이드-워셜의 최소가중치를 구하는 문제에서는, 일반적으로 3중 for문 안에 min()함수를 사용한다. 하지만 이 문제에서는 연관관계만 알면 되기에, 이에 맞게 체크만 해준다.
• min() 연산으로 인해 수행시간이 늘어나서 시간초과가 발생하게 되는 경우가 생기는데, 이를 방지해준다.