[백준][python]2458 키 순서

문제

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

소스코드

if __name__ == "__main__":
    n,m = map(int,input().split())
    res = 0
    arr = [[0] * (n+1) for _ in range(n+1)]
    for _ in range(m):
        tall,short = map(int,input().split())
        arr[tall][short] = 1

    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                if arr[i][j] == 1 or (arr[i][k] == 1 and arr[k][j] == 1):
                    arr[i][j] = 1 # i -> j 가 연결되었는지?
    for i in range(1,n+1):
        cnt = 0
        for j in range(1,n+1):
            cnt += (arr[i][j] + arr[j][i])
        if cnt == (n-1):
            res +=1
    print(res)

설명

• 플로이드-와샬 알고리즘을 이용해서 각 노드가 연결되어 있는지 체크한다 (최소값을 구하는 기존 플로이드 와샬이 아님)
• 크거나 작음을 확인할 수 있다면 간선을 통해 단방향 이동을 할 수 있다.
• 나보다 작은 노드에 갈 수 있다.
• 나에게 오면 나보다 큰 노드이다.
• 예를 들어 다음과 같이 간선의 정보가 주어졌다고 생각하자 (문제 예시)

 

arr[tall][small] 로 배열을 기록하면 위의 표와 같다.

[4][2] 4가 2보다 크고 [4][6] 4가 6보다 큼을 알 수있다.

열을 살펴보면 [3][4] 은 3이 4보다 크고, [5][4]은 5가 4보다 큼을 알 수 있다.

 

누적해서 확인하면 i - > j  i보다 j이 작은지 확인하려면 i에서  j로 갈 수 있는지 확인하면 된다.

플로이드 와샬 알고리즘을 사용해서 다른 노드를 경유해서 갈 수 있는지 확인하면 된다.

나보다 작은 값 + 나보다 큰 값이 나를 제외한 전체노드-1 이면 정확한 위치를 알 수 있다.