38_정확한 순위

최단 거리 문제이다.

책 풀이는 플로이드-워셜 알고리즘을 활용해서 풀었으나, 나는 다익스트라 알고리즘 같은 느낌의 알고리즘을 사용해서 풀었다.

 

---

내  풀이

# 정확한 순위
import sys, heapq
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split()) # n은 학생 수, m은 두 학생의 성적을 비교한 횟수
graph = [[] for _ in range(n+1)]
connected = [[False] * (n+1) for _ in range(n+1)] # connected[i][j] = i->j로 연결되어 있는지 여부를 저장

# 성적 비교 입력
for _ in range(m):
    a, b = map(int, input().split()) # a번 학생이 b번 학생보다 성적이 낮다.
    graph[a].append(b)


# start보다 큰 수의 경우 connected[start][i] = True로 바꾸는 함수
def dijkstra(start):
    q = []
    heapq.heappush(q, start)
    while q:
        now = heapq.heappop(q)


        for i in graph[now]:
            if not connected[start][i]:
                connected[start][i] = True
                heapq.heappush(q, i)


# num이 순위를 확인할 수 있는 숫자인지 확인하는 함수
def check_rank(num):
    row = connected[num][1:]
    more_than_num = row.count(True)

    less_than_num = 0
    for i in range(1, n+1):
        if connected[i][num]:
            less_than_num += 1
    
    if more_than_num + less_than_num == n - 1:
        return True
    else:
        return False


# 1~n번까지의 학생과 연결된 학생들을 찾는다.
for i in range(1, n+1):
    dijkstra(i)

# i가 순위를 확인할 수 있는 숫자인지 확인하는 함수
answer = 0
for i in range(1, n+1):
    if check_rank(i):
        print(i)
        answer += 1

print(answer)

 

dijkstra함수를 통해서 시작 학생과 연결된 학생의 경우 conencted[start][i]를 true로 만든다.

dijkstra함수를 1~N번 학생까지 돌리면, connected[i][j] = i에서 시작해서 j까지 경로가 있으면 True, 없으면 False 저장된다.

 

그리고 check_rank함수를 통해, 해당 학생의 순위를 정확하게 알 수 있는지 확인한다.

n번 학생이 있다면, 

n번 학생보다 큰 숫자의 개수 + n번 학생보다 작은 숫자의 개수 = 전체 숫자의 개수 - 1 인 경우 순위를 정확하게 파악할 수 있다.

 

 

---

다른 풀이

 

A에서 B로 도달이 가능하다는 것 = A가 B보다 성적이 낮다는 의미

 

A에서 B로 도달이 가능하거나, B에서 A로 도달이 가능하면, A와 B의 성적 비교가 가능한 것

 

학생 수가 500 이하 이므로 O(N^3)의 시간 복잡도로 동작하는 플로이드 워셜 알고리즘을 이용해 문제 해결 가능

-> 가능한가?

 

따라서 플로이드워셜 알고리즘을 수행한 후에 모든 노드에 대하여 다른 노드와 서로 도달이 가능한지를 체크하여 문제를 해결할 수 있다.

이 때 자기자신은 항상 도달 가능하다고 보고, 카운트를 진행한다.

결과적으로 특정한 노드의 카운트 값이 N이라면, 해당 노드의 정확한 순위를 알 수 있다.

 

풀이 코드

INF = int(1e9)

n, m = map(int, input().split())
graph = [[INF] * (n+1) for _ in range(n+1)]

for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0


for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1


for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][k] + graph[k][b], graph[a][b])

for g in graph:
    print(g)


result = 0
# 각 학생을 번호에 따라 한 명씩 확인하여 도달 가능한지 체크
for i in range(1, n+1):
    count = 0
    for j in range(1, n+1):
        if graph[i][j] != INF or graph[j][i] != INF:
            count += 1
    if count == n:
        result += 1

print(result)

 

---

결국 핵심 아이디어는 본인 + start부터 연결된 경로 개수 + start까지 연결되어진 경로 개수 = 학생 수 인 경우 순위를 정확하게 알 수 있다는 것이다.