[파이썬] 백준 18128 : 치삼이의 징검다리 건너기 (골드1)

[파이썬] 백준 18128 : 치삼이의 징검다리 건너기 (골드1)

• https://www.acmicpc.net/problem/18128

---

풀이

방향성 생각

• 시작 / 도착 위치는 항상 밟을 수 있다는 예외처리하기.
• BFS로 물이 퍼져나가는 시간을 구한다.
• fountains에 water src를 받아놓고, flood에 물이 퍼진 시간을 기록한다.
• 이후, 다익스트라를 사용해서 (t,x,y)를 힙에 넣는다.
  • t는 현재가지 가장 작은 flood를 갱신하면서 힙에 넣는다.

 

---

파이썬

from collections import deque
import sys
import heapq as hq

input = lambda : sys.stdin.readline().strip()
inside = lambda x,y: 0<=x<N and 0<=y<N
INF = float('inf')
wdires = [(1,0),(0,1),(-1,0),(0,-1)]
cdires = [(j,i) for i in range(-1,2) for j in range(-1,2) if abs(i) + abs(j)]

N,W = map(int,input().split())

fountains = deque()
flood = [[-1]*N for _ in range(N)]
for _ in range(W):
    y,x = map(lambda x : int(x) - 1, input().split())
    flood[y][x] = 0
    fountains.append((x,y))

arr = [list(map(int,input())) for _ in range(N)]

while fountains:
    x,y = fountains.popleft()
    for dx,dy in wdires:
        nx,ny = x+dx,y+dy
        if inside(nx,ny) and flood[ny][nx] == -1:
            flood[ny][nx] = flood[y][x] + 1
            fountains.append((nx,ny))

flood[0][0] = 0
flood[-1][-1] = 0

V = [[INF]*N for _ in range(N)]
V[0][0] = 0
heap = [(0,0,0)]
while heap:
    t,x,y = hq.heappop(heap)

    if t > V[y][x]:
        continue

    for dx,dy in cdires:
        nx,ny = x+dx,y+dy

        if inside(nx,ny) and arr[ny][nx]:
            nt = max(t,flood[ny][nx])
            if nt < V[ny][nx]:
                hq.heappush(heap,(nt,nx,ny))
                V[ny][nx] = nt

print(V[-1][-1] if V[-1][-1] != INF else -1)

---

코멘트

• 별로 어렵진 않은 문제.