[TIL #23] 23일차 오늘의 공부 (2023.03.25 토)

TIL 2023.03.25 🐣

수 ~ 금 TIL을 작성하지 않았는데,,,, 공부를 안한건 아니고 작성하는걸 잊었습니다.... 실망스럽네요 저자신에게...

오늘 배운 것 👩🏻‍💻

알고리즘

• 백준 1389 : 케빈베이컨 수가 최소인 사람 구하기
  • 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합
  • 플로이드 워셜 알고리즘을 사용하면 쉽게 풀 수 있는 문제이다. 그런데 오랜만에 구현했더니 사실 기억이 잘 안나서 애를 먹었다.

    # 케빈베이컨 : 케빈 베이컨의 수가 가장 작은 사람을 출력   
    # 플로이드 워셜 알고리즘 구하기
    import sys
    n, m = map(int, sys.stdin.readline().rstrip().split())
    graph = [[0] * n for _ in range(n)]
    
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        graph[a - 1][b - 1] = 1
        graph[b - 1][a - 1] = 1
    
    for i in range(n):
        for j in range(n): 
            for k in range(n):
                if j == k:
                    continue            
    
                if graph[j][i] and graph[i][k]: # j에서 i를 거쳐 k로 갈 수 있다면
                    if graph[j][k] == 0:    # j - k 연결되지 않은 경우
                        graph[j][k] = graph[j][i] + graph[i][k]
                    else:
                        graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])
    result_idx = 0
    min_count = 10e9
    for i in range(n):
        count = 0
        for j in range(n):
            count += graph[i][j]   # i의 케빈 베이컨 수 구하기
        if min_count > count:
            min_count = count
            result_idx = i
    
    print(result_idx + 1)

React

• 리액트 강의 섹션 2 정리 내용을 포스팅 했다. 내용이 길어서 두 개의 포스팅으로 나눠 올릴 예정이다.

기타 🤔

추가적으로 하면 좋을 것