[Python] 프로그래머스. 배달 (Level 3)

https://programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달 | 프로그래머스

 

가중치가 들어간 그래프에서, 조건을 충족하는 bfs를 구현하는 문제.

 

 

	import math
	from collections import deque
	def bfs(start, maps, distance, K):
	queue = deque()
	queue.append(start)
	# 처음 출발한 도시의 distance는 0
	distance[start] = 0
	while queue:
	y = queue.popleft()
	for x in range(1, len(maps)):
	# 도착할 수 있는 도시인 경우
	if maps[y][x] != 0:
	# 해당 마을까지의 거리가 현재까지의 거리 + 이동할 때 걸리는 거리보다 작다
	# 현재까지의 거리 + 이동할 때의 거리가 K보다 작다 (문제 조건)
	if distance[x] > distance[y] + maps[y][x] and distance[y]+maps[y][x] <= K:
	distance[x] = distance[y] + maps[y][x]
	queue.append(x)
	# distance 값 중 K보다 작은 값의 개수만 리턴한다.
	return len([i for i in distance if i <= K])
	def solution(N, road, K):
	# 시작지점 1에서부터 해당 마을까지의 거리.
	# 초기값을 inf로 설정하고, 계산한 거리가 distance[마을]보다 작으면 distance를 업데이트해준다.
	distance = [math.inf for _ in range(N+1)]
	# 마을 그래프 그리기
	maps = [[0 for _ in range(N+1)] for _ in range(N+1)]
	for frm, to, w in road:
	# 0이면 초기화한 값 그대로이므로 w값을 넣어준다
	if maps[frm][to] == 0 and maps[to][frm] == 0:
	maps[frm][to], maps[to][frm] = w, w
	else:
	# 중복된 값이 있을 경우, 가장 작은 weight만 사용한다.
	if w < maps[frm][to]:
	maps[frm][to], maps[to][frm] = w, w
	return bfs(1, maps, distance,K)

view raw [프로그래머스] 배달.py hosted with ❤ by GitHub