문제 설명
1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.
- 1번 학생의 키 < 5번 학생의 키
- 3번 학생의 키 < 4번 학생의 키
- 5번 학생의 키 < 4번 학생의 키
- 4번 학생의 키 < 2번 학생의 키
- 4번 학생의 키 < 6번 학생의 키
- 5번 학생의 키 < 2번 학생의 키
이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다.
1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다. 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다.
학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.
- 입력
- 첫째 줄에 학생들의 수 N (2 ≤ N ≤ 500)과 두 학생 키를 비교한 횟수 M (0 ≤ M ≤ N(N-1)/2)이 주어진다.
- 다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 N보다 작거나 같은 서로 다른 양의 정수 a와 b가 주어진다. 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다.
- 출력
- 자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다.
입출력 예시
예제 입력 1
6 6
1 5
3 4
5 4
4 2
4 6
5 2예제 입력 2
6 7
1 3
1 5
3 4
5 4
4 2
4 6
5 2예제 입력 3
6 3
1 2
2 3
4 5예제 출력 1
1예제 출력 2
2예제 출력 3
0문제 풀이
해당 문제는 노드의 수와 노드들의 우열 관계가 주어지고, 순위가 결정되는 노드의 개수를 출력하는 문제이다.
해당 문제는 플로이드 워셜 알고리즘을 이용해 풀 수 있는데, 이를 위해 NxN 크기의 인접 행렬 그래프를 만든다.
graph[i][j]는 i번째 노드가 j번째 노드보다 우월하다(키가 크다)는 뜻이고 이를 간선의 방향으로 표현한 것이다. a→k, k→b 이면, a→b 가능함을 graph에 표시한다.
이 과정에서 플로이드 워셜 알고리즘을 이용한다. 이렇게 간접적으로 접근이 가능한 간선들도 graph에 표시되면, graph를 통해서 순위가 결정되는지 확인할 수 있다.
V번 노드가 순위가 결정됐는지 확인하기 위해서는, V번 노드를 제외한 다른 모든 노드들과 비교했을 때, 이기거나 진 정보가 확실히 있어야 한다.
즉 V번 노드를 제외한 모든 노드와 간선이 방향에 상관없이 연결이 되어 있다는 뜻이다.
이를 코드로 구현하면 아래와 같다.
CODE
import sys
input = sys.stdin.readline
def solution():
N, M = map(int, input().split())
INF = int(1e9)
graph = [[INF] * (N+1) for _ in range(N+1)]
for i in range(1, N+1):
graph[i][i] = 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][b], graph[a][k] + graph[k][b])
answer = 0
for v in range(1, N+1):
# v 번 노드가 순위가 정해져있는지 확인
for i in range(1, N+1):
if graph[i][v] < INF or graph[v][i] < INF:
continue
else:
break
else: # 위 for 문을 다 돌았다면
answer += 1
print(answer)
if __name__ == "__main__":
solution()시간 복잡도
