[파이썬] 백준 1261 : 알고스팟 (골드4)

[파이썬] 백준 1261 : 알고스팟 (골드4)

1261번: 알고스팟

---

문제

---

풀이

0. 방향성 생각

• 다익스트라. 특정 지점 도달하는데 걸린 최소 벽뿌횟수 저장

1. 입력

import heapq as hq
import sys
input = lambda: sys.stdin.readline().rstrip()

w,h = map(int,input().split())
INF = w*h
arr = [list(input()) for _ in range(h)]
visit = [[INF]*w for _ in range(h)]
step = [(1,0),(0,1),(-1,0),(0,-1)]

• 최대 벽뿌횟수는 w*h-2이다. INF를 w*h로 설정
• visit은 arr과 같은 크기로 저장. visit에 최소 벽뿌횟수 갱신

2. 탐색

heap = []
hq.heappush(heap,(0,0,0))
while True:
    
    t,x,y = hq.heappop(heap)
    if (x,y) == (w-1,h-1):
        print(t)
        break
    
    for dx,dy in step:
        nx = x + dx
        ny = y + dy
        if 0<=nx<w and 0<=ny<h:
            if arr[ny][nx] == '0' and t < visit[ny][nx]:
                hq.heappush(heap,(t,nx,ny))
                visit[ny][nx] = t
            elif arr[ny][nx] == '1' and t+1 < visit[ny][nx]:
                hq.heappush(heap,(t+1,nx,ny))
                visit[ny][nx] = t+1

• 0일 경우 벽뿌횟수 t, 1일 경우 벽뿌횟수 t+1
• 갱신하는 경우에만 추가하기

 

---

전체코드

import heapq as hq
import sys
input = lambda: sys.stdin.readline().rstrip()

w,h = map(int,input().split())
INF = w*h
arr = [list(input()) for _ in range(h)]
visit = [[INF]*w for _ in range(h)]
step = [(1,0),(0,1),(-1,0),(0,-1)]

heap = []
hq.heappush(heap,(0,0,0))
while True:
    
    t,x,y = hq.heappop(heap)
    if (x,y) == (w-1,h-1):
        print(t)
        break
    
    for dx,dy in step:
        nx = x + dx
        ny = y + dy
        if 0<=nx<w and 0<=ny<h:
            if arr[ny][nx] == '0' and t < visit[ny][nx]:
                hq.heappush(heap,(t,nx,ny))
                visit[ny][nx] = t
            elif arr[ny][nx] == '1' and t+1 < visit[ny][nx]:
                hq.heappush(heap,(t+1,nx,ny))
                visit[ny][nx] = t+1

 

다시 풀어본 풀이

import heapq as hq
import sys
input = lambda : sys.stdin.readline().rstrip()

inf = 1e9
w,h = map(int,input().split())
arr = [list(map(int,input())) for _ in range(h)]
dire = [(1,0),(0,1),(-1,0),(0,-1)]
visit = [[1e9]*w for _ in range(h)]
visit[0][0] = 0

heap = []
hq.heappush(heap,(0,0,0))
while heap:
    cost,x,y = hq.heappop(heap)

    for dx,dy in dire:

        nx = x + dx
        ny = y + dy

        if 0<=nx<w and 0<=ny<h:
            if arr[ny][nx] and cost + 1 < visit[ny][nx]:
                visit[ny][nx] = cost + 1
                hq.heappush(heap,(cost+1,nx,ny))
            if not arr[ny][nx] and cost < visit[ny][nx]:
                visit[ny][nx] = cost
                hq.heappush(heap,(cost,nx,ny))

print(visit[-1][-1])

비슷한듯?

 

코멘트

.