kingsubin

BOJ)1389 - 케빈 베이커의 6단계 법칙 본문

PS/boj

BOJ)1389 - 케빈 베이커의 6단계 법칙

kingsubin 2022. 9. 24. 12:54
  • 최소 거리랑 그래프 보고 BFS 생각함.
  • V, E 갯수 제한 보고 인접 리스트 생각함.
  • search 함수에서 전부 방문했으면 안 돌아도 되는거 처리 할 수 있는거 같은데 시간 문제 없어서 넘어감.
  • 문법 헷갈려서 아직 콘솔 안 찍어보면 삐걱거림.
  • 풀이 너무 오래 걸림.
import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
board = [[] for _ in range(N + 1)]

for _ in range(M):
    x, y = map(int, input().split())
    board[x].append(y)
    board[y].append(x)

def search(x):
    dq = deque()
    check = [False] * (N + 1)
    check[x] = True
    total = 0

    for i, v in enumerate(board[x]):
        dq.append((v, 1))

    while dq:
        pop = dq.popleft()
        num = pop[0]
        d = pop[1]

        if not check[num]:
            check[num] = True
            total += d

            for j in board[num]:
                if not check[j]:
                    dq.append((j, d + 1))

    return total

count = [0 for _ in range(N + 1)]
for i in range(1, N + 1):
    count[i] = search(i)

print(count.index(min(count[1:])))

 


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

'PS > boj' 카테고리의 다른 글

BOJ)1915 - 가장 큰 정사각형  (0) 2022.09.25
BOJ)15686 - 치킨배달  (0) 2022.09.22
boj)2250 - 트리의 높이와 너비  (0) 2020.12.12
boj)1991 - 트리 순회  (0) 2020.12.11
boj)7562 - 나이트의 이동  (0) 2020.12.10
0 Comments
댓글쓰기 폼