티스토리 뷰
- 최소 거리랑 그래프 보고 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:])))
반응형
'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 |
링크
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
TAG
- 백기선 스터디
- 이펙티브자바 아이템59
- 김영한 http
- REST API
- Spring Security
- 백준
- GCP
- dreamcoding
- 이펙티브자바 아이템60
- 프로그래머스
- 이펙티브자바
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- 패스트캠퍼스 컴퓨터공학 완주반
- 프로그래머스 SQL
- 이펙티브자바 스터디
- HTTP 완벽가이드
- 모던자바스크립트
- java
- 김영한 JPA
- 집 구하기
- 킹수빈닷컴
- 드림코딩
- BOJ
- JS 딥다이브
- js promise
- JPA 연관관계 매핑
- js api
- http
- js array
- HTTP 완벽 가이드
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |
글 보관함