99클럽 코테 스터디 3일차 TIL, Floyd-Warshall

• 문제: Baekjoon2660: 회장뽑기
  • 설명: 그래프가 주어질 때 다른 노드까지의 가장 큰 최단 거리가 가장 작은 노드들을 구하여라
  • 다시 설명하자면 한 노드에서 모든 노드들까지의 최단 거리를 구하자. 그리고 한 노드의 점수는 이 최단 거리 중 가장 큰 값이다.
    • 예) 1번 노드와 2번 노드의 최단 거리가 2, 1번 노드와 3번 노드의 최단 거리가 3이면 1번 노드의 점수는 3이다.
  • 최종적으로 점수가 가장 작은 노드들을 구하는 문제이다.
• 풀이
  • 일단 모든 노드 쌍의 최단 거리를 구하여야하니 Floyd-Warshall을 적용한다.
  • 각 점수에 속하는 노드들을 배열에 저장한다.
  • 가장 작은 점수에 속하는 노드들을 출력한다.
• 오늘의 회고
  • range로 모든 인덱스 탐색하는 형태를 쓰고 싶지 않은데 그렇다고 슬라이싱 또한 쓰고 싶지 않아서 굉장히 딜레마이다.
    • range를 안쓴다면...

      for idx, adj in enumerate(adj_mat[1:]):
      score = max(adj[1:])
      friend_list[score].append(idx)

    • range를 쓴다면...

      for i in range(1, n + 1):
      score = max(adj_mat[i][1:])
      friend_list[score].append(i)

  • 언어가 달라졌다고 사람의 뇌가 바뀌나보다. 파이썬으로 생각하려니까 자꾸 멈칫 멈칫하게 되고 코드가 잘 떠오르지 않는다.
    • 조금 더 많이 풀어볼 필요가 있다고 느꼈다.
  • 그리고 이 문제 또한 그래프의 가중치가 없기 때문에 BFS로 충분히 풀리는 문제이다.

Code

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

INF = 0x3f3f3f3f

n = int(input())

adj_mat = [[INF for _ in range(n + 1)] for _ in range(n + 1)]

for i in range(1, n + 1):
    adj_mat[i][i] = 0

a, b = map(int, input().split())
while not (a == -1 and b == -1):
    adj_mat[a][b] = 1
    adj_mat[b][a] = 1

    a, b = map(int, input().split())

for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            adj_mat[i][j] = min(adj_mat[i][j], adj_mat[i][k] + adj_mat[k][j])

friend_list = [[] for _ in range(n + 1)]
for i in range(1, n + 1):
    score = max(adj_mat[i][1:])

    friend_list[score].append(i)

ans = 0
while ans < n and len(friend_list[ans]) == 0:
    ans += 1

print(ans, len(friend_list[ans]))
print(*friend_list[ans])