백준[17616] 등수 찾기 (Python3)

전형적인 그래프 탐색 문제를 응용했다.

이 문제에서 주목할 점은, 정점 X와 뒤, 앞으로 연결된 정점 개수를 파악하는 것이다.
즉, bfs를 두 번 돌려야 한다.

예제 3을 기준으로 보면
우리가 보려는 노드는 정점 1이니, 이 기준으로 본다면
정점 1과 3이 연결돼있고, 3은 4, 5와 연결돼있으니, 정점 1의 뒤엔 3, 4, 5가 있다.
정리하면, 정점1의 뒤에 있는 정점 개수는 3고, 앞에  있는 정점 개수는 0개다.

반면, 정점 2는 정점 1과 어떤 방향으로 연결돼있는지 알 수 없다.
정점 3보다 앞에 있단 것만 알지, 정점 1의 어느쪽에 연결돼는지를 알 수 없다.
다행인건 문제에서 가능한 등수의 최소, 최대만 구하는 것이기 때문에, 애매한 정점들은 하나의 경우에 묶어 생각할 수 있다.

1. 정점 1보다 왼쪽에 있다.
2. 정점 2보다 오른쪽에 있다.

나는 이 부분에 대한 처리를 그냥, 1 + 앞의 노드 개수, N - 뒤의 노드 개수로 처리했다.
1 + 앞의 노드 개수의 경우, 애매한 정점들은 다 뒤에 있다고 가정됐고,
N - 뒤의 노두 개수의 경우, 애매한 정점들은 다 앞에 있다고 가정됐기 때문이다.

 

from collections import deque
N, M, X = map(int, input().split())
backs = [[] for _ in range(N + 1)]
fronts = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v = map(int, input().split())
    backs[u].append(v)
    fronts[v].append(u)

front, back = 0, 0
visit = [False] * (N + 1)
q = deque([X])
while q:
    here = q.popleft()
    for there in backs[here]:
        if visit[there]:
            continue
        visit[there] = True
        back += 1
        q.append(there)

q = deque([X])
while q:
    here = q.popleft()
    for there in fronts[here]:
        if visit[there]:
            continue
        visit[there] = True
        front += 1
        q.append(there)
print(1 + front, N - back)