-
21278 bfs ==> 다시 풀어보기코테 대비 python/백준 2023. 1. 27. 21:32
https://www.acmicpc.net/problem/21278
from itertools import combinations from collections import deque import sys def input(): return sys.stdin.readline().rstrip() N, M = map(int, input().split()) graph = {i: [] for i in range(1, N+1)} for _ in range(M): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) def bfs(start1, start2, graph, N): result = [99999999 for _ in range(N+1)] result[0] = 0 # 인덱스 0은 더미 result[start1] = 0 result[start2] = 0 q = deque() q.append((start1, 0)) q.append((start2, 0)) visit = set() visit.add(start1) visit.add(start2) while q: if len(visit) == N: break cur, dist = q.popleft() for nxt in graph[cur]: if nxt in visit: continue visit.add(nxt) q.append((nxt, dist + 1)) result[nxt] = dist + 1 return sum(result) def solution(graph, N): candidate = [i for i in range(1, N+1)] answer = 99999999 fin_store1 = N+1 fin_store2 = N+1 for comb in combinations(candidate, 2): store1, store2 = comb result = bfs(store1, store2, graph, N) if answer > result: fin_store1 = store1 fin_store2 = store2 answer = result elif answer == result: if fin_store1 > store1: fin_store1 = store1 fin_store2 = store2 answer = result elif fin_store1 == store1: if fin_store2 > store2: fin_store1 = store1 fin_store2 = store2 answer = result return ' '.join(map(str, [fin_store1, fin_store2, answer * 2])) print(solution(graph, N))
'코테 대비 python > 백준' 카테고리의 다른 글
10950 함수만들기 (0) 2023.01.30 21315 완전탐색 블루트포스 ==> 다시풀기 (0) 2023.01.27 16987 dfs, 백트레킹 ==> 다시풀어보기 (0) 2023.01.27 1969 문자열, 구현 (0) 2023.01.27 16174 dfs, bfs (0) 2023.01.26