-
알고리즘: 백준 4485번 녹색 옷 입은 애가 젤다지? (feat. python)알고리즘/백준(BaekJoon) 2021. 1. 12. 20:02
import sys import heapq read = sys.stdin.readline def problem(): N = int(read()) if N == 0: return -1 cave = [list(map(int, read().split()))for _ in range(N)] dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] visit = [[False for _ in range(N)] for _ in range(N)] hq = [] heapq.heappush(hq, [cave[0][0], [0, 0]]) answer = -1 while hq: cw, cn = heapq.heappop(hq) if cn[0] == N-1 and cn[1] == N-1: answer = cw break if visit[cn[1]][cn[0]]: continue visit[cn[1]][cn[0]] = True for i in range(4): nx = cn[0] + dx[i] ny = cn[1] + dy[i] if 0 <= nx < N and 0 <= ny < N and not visit[ny][nx]: heapq.heappush(hq, [cw + cave[ny][nx], [nx, ny]]) return answer i = 1 while True: answer = problem() if answer == -1: break else: print("Problem {}: {}".format(i, answer)) i += 1
반응형'알고리즘 > 백준(BaekJoon)' 카테고리의 다른 글
알고리즘: 백준 11779번 최소비용 구하기2 (feat.python) (0) 2021.01.15 알고리즘: 백준 2665번 미로만들기 (feat.python) (0) 2021.01.13 알고리즘: 백준 13549번 숨바꼭질 (feat. python) (0) 2021.01.12 알고리즘: 백준 1504번 특정한 최단 경로 (feat. python) (0) 2021.01.12 알고리즘: 백준 1238번 파티 (feat. python) (0) 2021.01.11