17616번: 등수 찾기
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어
www.acmicpc.net
코드
from collections import deque
n, m, x = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
a, b = map(int, input().split()) # a가 b보다 잘함
graph[a].append((b, 1))
graph[b].append((a, -1))
def bfs(start, dir):
res = 0
q = deque([start])
visited = [False]*(n+1)
visited[start] = True
while q:
now = q.popleft()
for nx, d in graph[now]:
if not visited[nx] and d == dir:
q.append(nx)
visited[nx] = True
res += 1
return res
high = bfs(x, -1)+1
low = bfs(x, 1)
print(high, n-low)
BFS를 이용하여 나보다 확실히 낮은 등수의 사람과 높은 등수의 사람의 명수를 구하면 된다. 이를 위해 처음에 입력받을 때 나보다 높은 등수인 관계는 1, 낮은 등수인 관계는 -1로 저장해놓았다.
Python3로는 12점이지만 PyPy3로는 100점이 나온다. 아마 시간 문제 때문인 것 같다.
인접리스트로 BFS를 구현했을 때의 시간복잡도는 O(V+E)(V는 정점의 개수, E는 간선의 개수)이므로 조건이 N ≤ 1,000, M = N(N-1)/2인 서브태스크2에서는 시간복잡도가 O(N^2)라고 할 수 있는데...파이썬은 1초에 대략 2천만번의 연산을 할 수 있다고 한다. 그렇기 때문에 서브태스크 2는 통과될 것 같은데 안된다....
'문제풀이 > DFS_BFS' 카테고리의 다른 글
[Python/파이썬] 백준 1303번 전쟁 - 전투 (0) | 2024.04.22 |
---|---|
[Python/파이썬] 백준 15644번 구슬 탈출 3 (0) | 2024.04.21 |
[Python/파이썬] 백준 14923번 미로 탈출 (1) | 2024.04.07 |
[Python/파이썬] 백준 15900번 나무 탈출 (1) | 2024.03.29 |
[Python/파이썬] 백준 16985번 Maaaaaaaaaze (1) | 2024.03.28 |