[Python] 프로그래머스. 2020 카카오 인턴 - 경주로 건설 (Level 3)

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

코딩테스트 연습 - 경주로 건설

bfs 기반 탐색 문제이면서, 경로의 최소비용을 체크하는 문제.

 

 

 

	import math
	from collections import deque
	def solution(board):
	def bfs(start):
	# table[y][x] = 해당 위치에 도달하는 최솟값.
	table = [[math.inf for _ in range(len(board))] for _ in range(len(board))]
	# 진행 방향. 위 - 0, 왼쪽 - 1, 아래 = 2, 오른쪽 = 3
	dirs = [(-1,0),(0,-1),(1,0),(0,1)]
	queue = deque([start])
	# 처음 위치의 비용 = 0
	table[0][0] = 0
	while queue:
	# y좌표, x좌표, 비용, 진행방향
	y, x, cost, head = queue.popleft()
	for idx, (dy, dx) in enumerate(dirs):
	ny, nx = y + dy, x + dx
	# 진행방향과 다음 방향이 일치하면 + 100, 다르면 전환비용 500 + 진행비용 100 = 600
	n_cost = cost + 600 if idx != head else cost + 100
	# board[y][x] == 0 : 진행방향에 벽이 없음. table[ny][nx] > n_cost : 다음 좌표의 최솟값보다 진행방향 비용이 작을 경우
	if 0 <= ny < len(board) and 0 <= nx < len(board) and board[ny][nx] == 0 and table[ny][nx] > n_cost:
	# table 좌표 업데이트.
	table[ny][nx] = n_cost
	queue.append((ny, nx, n_cost, idx))
	return table[-1][-1]
	return min(bfs((0,0,0,2)), bfs((0,0,0,3)))

view raw [프로그래머스] 경주로 건설.py hosted with ❤ by GitHub