[Python] 백준 1261. 알고스팟

https://www.acmicpc.net/problem/1261

1261번: 알고스팟

 

BFS를 사용하지만, BFS에서 사용하는 queue를 heap 자료구조로 활용해야 하는 독특한 문제.

heap을 사용하는 이유는 '벽을 가장 적게 부수고 이동하는 경우'가 항상 우선순위에 위치한 채 BFS로 순회해야 하기 때문.

 

이 개념을 생각 못해서 문제를 푸는 데 정말 오래 걸렸다.

 

	import sys
	import heapq
	N, M = map(int, sys.stdin.readline().split())
	maps = []
	for _ in range(M):
	maps.append(list(sys.stdin.readline()))
	visited = [[0 for _ in range(N)] for _ in range(M)]
	def bfs(start, maps, visited):
	dirs = [(1,0),(0,1),(0,-1),(-1,0)]
	queue = []
	heapq.heappush(queue, start)
	while queue:
	cnt, y, x = heapq.heappop(queue)
	visited[y][x] = 1
	if y == M - 1 and x == N - 1:
	return cnt
	for dy, dx in dirs:
	ny, nx = y + dy, x + dx
	if 0 <= ny < M and 0 <= nx < N and not visited[ny][nx]:
	visited[ny][nx] = 1
	if maps[ny][nx] == "0":
	heapq.heappush(queue, (cnt, ny, nx))
	elif maps[ny][nx] == "1":
	heapq.heappush(queue, (cnt + 1, ny, nx))
	print(bfs((0,0,0), maps, visited))

view raw [백준] 알고스팟.py hosted with ❤ by GitHub