출처 : 이것이 취업을 위한 코딩테스트다 with Python, 숨바꼭질
더보기
다익스트라 풀이
import sys
from collections import Counter
from heapq import heappop, heappush
INF = float('inf')
def solution(n, pass_list):
#1번으로부터 최단 거리가 가장 먼 노드를 찾음.
ad_matrix = [[INF for _ in range(n)] for _ in range(n)]
# 인접 행렬 초기화
for h1, h2 in pass_list:
ad_matrix[h1 - 1][h2 - 1] = 1
ad_matrix[h2 - 1][h1 - 1] = 1
min_dis = [INF for _ in range(n)]
heap = []
visited_set = set()
heappush(heap, (0, 0))
min_dis[0] = 0
while len(heap) > 0:
current_dis, node_idx = heappop(heap)
if node_idx in visited_set:
continue
visited_set.add(node_idx)
# 인접한 노드를 찾아 최소 거리 갱신
for near_node_idx in range(n):
near_node_dis = ad_matrix[node_idx][near_node_idx]
if near_node_dis == INF:
continue
# 인접하다면, 최소 거리 갱신
min_dis[near_node_idx] = min(min_dis[near_node_idx], current_dis + near_node_dis)
# 우선순위 큐에 넣음
heappush(heap, (min_dis[near_node_idx], near_node_idx))
# 가장 거리가 먼 노드를 찾음.
counting_dis = Counter(min_dis)
max_dis, node_idx = sorted([(min_dis[i], i) for i in range(n)], key = lambda x: (-x[0], x[1]))[0]
return (node_idx + 1, max_dis, counting_dis[max_dis])
n, m = map(int, input().split())
pass_list = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(m)]
print(solution(n, pass_list))
BFS 풀이
이 문제는 가중치가 없는 그래프에서 최단 거리를 찾는 문제이다.
따라서, BFS로도 풀 수 있다.
다익스트라와 다른 점은 다익스트라는 최소 거리가 바로 나오지만,
BFS는 최소 거리를 BFS의 층을 계산해 간접적으로 구해야한다.
import sys
from collections import defaultdict, deque, Counter
from heapq import heappop, heappush
INF = float('inf')
def solution(n, pass_list):
# BFS
ad_list = defaultdict(lambda : [])
visited_set = set()
dis_dict = defaultdict(int)
for h1, h2 in pass_list:
ad_list[h1].append(h2)
ad_list[h2].append(h1)
queue = deque([1])
visited_set.add(1)
floor = 0 # 거리
floor_count = 1 # 거리 n에 해당하는 노드 개수
while len(queue) > 0:
current_node = queue.popleft()
dis_dict[current_node] = floor
floor_count -= 1
for near_node in ad_list[current_node]:
if near_node in visited_set:
continue
queue.append(near_node)
visited_set.add(near_node)
if floor_count == 0:
floor += 1
floor_count = len(queue)
# 가장 거리가 먼 노드를 찾음.
counting_dis = Counter(dis_dict.values())
node_idx, max_dis = sorted(list(dis_dict.items()), key=lambda x: (-x[1], x[0]))[0]
return (node_idx, max_dis, counting_dis[max_dis])
n, m = map(int, input().split())
pass_list = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(m)]
print(solution(n, pass_list))
Reference
'알고리즘 > Python' 카테고리의 다른 글
[python] 프로그래머스 - 순위 (0) | 2023.04.14 |
---|---|
[python] 프로그래머스 - 가장 먼 노드 (1) | 2023.04.14 |
[python] 이코테 - 화성 탐사 (0) | 2023.04.13 |
[python] 이코테 - 정확한 순위 (0) | 2023.04.13 |
[python] 백준 11404 - 플로이드 (0) | 2023.04.13 |