99클럽 코테 스터디 6일차 TIL + DFS

문제

Baekjoon2458: 키 순서
- 설명: 학생들의 키 순서가 주어질 때 자기 자신이 몇번째로 키가 큰지 알 수 있는 학생의 수를 구하여라

풀이

기본 개념

• 나의 위치를 아려면 (나보다 키가 큰 노드들의 수) + (키가 작은 노드들의 수) = $(n - 1)$ 이어야 한다.

키가 작은 노드들의 수 구하기

• 한 노드에서 시작해서 방문할 수 있는 노드들은 모두 자기 자신 보다 키가 큰 노드들
• 반대로 생각하면 나를 방문 한 노드들의 수가 나보다 키가 작은 노드들이다.
• DFS를 해주며 방문한 노드의 키가 작은 노드들의 수를 + 해준다.

키가 큰 노드들의 수 구하기

• 그렇다면 자기 자신보다 키가 큰 노드들의 수는 어떻게 구할까?
• 애초에 그래프를 만들 때 역방향 그래프도 같이 만들어준다.
• 이러면 자기 자신을 방문한 노드들의 수가 나보다 키가 큰 노드들이다.

오늘의 회고

• 말도 안된다! 이 문제도 플로이드 와샬이다!
• 플로이드 와샬을 생각하지 못하는 이유가 뭘까? 잘 몰라서일까?
• 조금 더 많은 문제를 풀어봐야겠다.
• 저 역방향 그래프 만드는 트릭은 SCC 구할 때 썼던 트릭이 생각나서 응용했다.
  • 역시 어려운 알고리즘을 공부한 것이 구현실력을 늘려주었을 뿐 아니라 여러 테크닉들을 공부할 수 있어서 좋았던 것 같다.

Code

# Baekjoon02458.py
import sys
input = sys.stdin.readline

visited = []

def dfs(adj_list, arr, curr):
    for adj in adj_list[curr]:
        if not visited[adj]:
            arr[adj] += 1
            visited[adj] = True
            dfs(adj_list, arr, adj)


n, m = map(int, input().split())

adj_list1 = [ [] for _ in range(n + 1) ] # 순방향 그래프
adj_list2 = [ [] for _ in range(n + 1) ] # 역방향 그래프

for _ in range(m):
    a, b = map(int, input().split())
    adj_list1[a].append(b)
    adj_list2[b].append(a)

# 나보다 키가 작은 노드들의 수 구하기
small = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
    visited = [False for _ in range(n + 1)]

    visited[i] = True
    dfs(adj_list1, small, i)

# 나보다 키가 큰 노드들의 수 구하기
big = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
    visited = [False for _ in range(n + 1)]

    visited[i] = True
    dfs(adj_list2, big, i)

ans = 0
for i in range(1, n + 1):
    if small[i] + big[i] == (n - 1):
        ans += 1

print(ans)