99클럽 코테 스터디 6일차 TIL - BFS (백준 2458번 - 키 순서)

https://www.acmicpc.net/problem/2458

• 오늘의 학습 키워드 : 플로이드 워셜, BFS
• 공부한 내용 -> 그림은 코드 설명

import sys
from collections import deque  # BFS 구현을 위한 deque 사용

# 학생 수 N과 비교 횟수 M을 입력 받음
N, M = map(int, sys.stdin.readline().strip().split())

# 각 학생에 대한 인접 리스트 생성
graph = [[] for _ in range(N + 1)]  # 자신보다 큰 학생들을 저장하는 그래프
reverse_graph = [[] for _ in range(N + 1)]  # 자신보다 작은 학생들을 저장하는 그래프

# 키 비교 관계 입력
for i in range(M):
    a, b = map(int, sys.stdin.readline().strip().split())  # a번 학생이 b번 학생보다 작음
    graph[a].append(b)  # a번 학생보다 큰 학생 b를 graph에 추가
    reverse_graph[b].append(a)  # b번 학생보다 작은 학생 a를 reverse_graph에 추가

# BFS 함수 정의
def bfs(start, graph):
    visited = [False] * (N + 1)  # 방문 여부를 확인하는 리스트
    queue = deque([start])  # 시작 노드를 큐에 추가
    visited[start] = True  # 시작 노드 방문 처리
    count = 0  # 도달 가능한 노드의 수

    while queue:
        node = queue.popleft()  # 큐에서 노드를 꺼냄
        for i in graph[node]:  # 현재 노드에 연결된 모든 노드 탐색
            if not visited[i]:  # 아직 방문하지 않은 노드인 경우
                visited[i] = True  # 방문 처리
                queue.append(i)  # 큐에 추가
                count += 1  # 도달 가능한 노드 수 증가

    return count  # 도달 가능한 노드의 총 수 반환

# 자신이 순위를 알 수 있는 학생 수 계산
answer = 0
for i in range(1, N + 1):  # 1번 학생부터 N번 학생까지 반복
    larger_count = bfs(i, graph)  # i번 학생보다 큰 학생 수 계산
    smaller_count = bfs(i, reverse_graph)  # i번 학생보다 작은 학생 수 계산

    # 자신보다 큰 학생 수 + 자신보다 작은 학생 수 == 전체 학생 수 - 1인 경우 순위를 알 수 있음
    if larger_count + smaller_count == (N - 1):
        answer += 1  # 순위를 알 수 있는 학생 수 증가

# 결과 출력
print(answer)  # 순위를 알 수 있는 학생 수 출력

• 오늘의 회고
  • 오늘의 미들러 문제는 https://www.acmicpc.net/problem/24444 로 이분탐색에 대한 문제였다. 그건 호로록 이분탐색을 많이해서 그런지 완벽하게 바로 풀지는 못해도 꽤나 나름 빠른 시간내에 풀어서 오늘은 챌린저 문제를 하나 더 풀기로 했다..
  • 챌린저 문제를 보고서 플로이드 워셜로 할라고 하니깐 시간초과가 날 것 같긴 했다. 물론 그래도 플로이드 워셜 문제를 안푼지 오래되어서 한번 풀어보긴 했다. 바로 시간초과가 나긴했지만 
    문제 풀때는 내가 풀었던 문제인 https://coooco.tistory.com/84 , https://coooco.tistory.com/90 이 둘 문제를 참고해서 풀었다. python으로 시간 초과나서 pypy3으로 하긴했다..

    

    import sys
    INF = int(1e9)  # 무한대를 나타내는 큰 수, 연결되지 않은 상태를 의미
    
    # 학생 수 N과 키 비교 횟수 M을 입력 받음
    N, M = map(int, sys.stdin.readline().strip().split())
    
    # N+1 x N+1 크기의 그래프를 INF로 초기화 (1부터 N까지 사용하기 위해 N+1 크기로 설정)
    graph = [[INF] * (N + 1) for _ in range(N + 1)]
    
    # 자기 자신에 대한 경로는 0으로 설정 (자기 자신과의 거리는 0)
    for i in range(N + 1):
        graph[i][i] = 0
    
    # 키 비교 정보를 입력 받아 그래프에 저장
    for i in range(M):
        a, b = map(int, sys.stdin.readline().strip().split())  # a번 학생이 b번 학생보다 키가 작음
        graph[b][a] = 1  # b에서 a로 가는 경로를 1로 설정 (a < b)
    
    # 플로이드-와샬 알고리즘: 모든 노드 간 최단 경로를 갱신
    for p in range(1, N + 1):  # 경유할 노드 p
        for i in range(1, N + 1):  # 시작 노드 i
            for j in range(1, N + 1):  # 도착 노드 j
                # i에서 j로 가는 경로와 i에서 p를 거쳐 j로 가는 경로 중 더 짧은 경로를 선택
                graph[i][j] = min(graph[i][j], graph[i][p] + graph[p][j])
    
    # 자신의 순위를 정확히 알 수 있는 학생 수 계산
    answer = 0
    for i in range(1, N + 1):
        smaller_count = 0  # i번 학생보다 작은 학생의 수
        larger_count = 0   # i번 학생보다 큰 학생의 수
    
        for j in range(1, N + 1):
            if graph[i][j] != INF:  # i에서 j로 도달할 수 있으면 j는 i보다 큼
                larger_count += 1
            if graph[j][i] != INF:  # j에서 i로 도달할 수 있으면 j는 i보다 작음
                smaller_count += 1
    
        # i번 학생이 자신의 위치를 알 수 있는 조건:
        # 자신보다 작은 학생 수 + 자신보다 큰 학생 수가 전체 학생 수 - 1과 같아야 함
        if smaller_count + larger_count - 1 == N:
            answer += 1  # 자신의 순위를 알 수 있는 학생 수 증가
    
    # 최종적으로 자신의 키 순위를 알 수 있는 학생 수 출력
    print(answer)

  • 그래서 푼 문제는 BFS 로 풀어야했다..