[백준 20926번] 얼음 미로(파이썬)

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

20926번: 얼음 미로

이 문제는 가중치가 있기 때문에

다익스트라를 쓰면 좋습니다.

다만, 이 문제는 일반적인 BFS,DFS와 다른 점이 있습니다.

바로 '한번에 쭉 간다'라는 것.

테라는 미끄러지면서 이동합니다.

상하좌우로 미끄러질 수 있는데

돌이나 출구를 만나기 전까지 미끄러집니다.

만약 범위를 벗어나거나

구멍을 만나면 아웃이고요.

그래서 한번에 쭉~~~미끄러진다는 걸 구현만 한다면

이 문제는 상대적으로 무난한게 풀 수 있었습니다.

#백준 20926번 얼음미로
from heapq import heappop,heappush

W,H=map(int,input().split())
room=[]


dx=[0,0,1,-1]
dy=[1,-1,0,0]
ex=0
ey=0
heap=[]
dist=[[1e9]*W for _ in range(H)]
answer=1e9
for i in range(H):
    tmp=input().rstrip()
    new=[0]*W
    for j in range(W):
        if tmp[j]=='T':
            new[j]=0
            heappush(heap,[0,i,j])
            dist[i][j]=0
        elif tmp[j]=='R':
            new[j]=-2
        elif tmp[j]=='H':
            new[j]=-3
        elif tmp[j]=='E':
            ex=i
            ey=j
            new[j]=-4
        else:
            new[j]=int(tmp[j])
    room.append(new)

def move(x,y,d):
    time=0
    path=[]
    while True:
        path.append(int(room[x][y]))
        x+=dx[d]
        y+=dy[d]
        if x<0 or x>=H or y<0 or y>=W:
            return x,y,1e9
        if room[x][y]==-3:
            return x,y,1e9

        if room[x][y]==-2:
            x-=dx[d]
            y-=dy[d]
            break
        if x==ex and y==ey:
            break

    time+=sum(path[1:])
    return x,y,time


while heap:

    cnt,x,y=heappop(heap)
    if cnt>dist[x][y]:
        continue

    for d in range(4):
        nx,ny,next_time=move(x,y,d)
        go_time=next_time+cnt
        if nx<0 or nx>=H or ny<0 or ny>=W:
            continue
        if dist[nx][ny]>go_time:
            dist[nx][ny]=go_time
            heappush(heap,[go_time,nx,ny])


answer=dist[ex][ey]
if answer==1e9:
    print(-1)
else:
    print(answer)

 

처음에는 move함수를 안만들었는데

틀려서 구글링해보니

move함수를 만들어주는 편이 좋은듯하더군요.

그리고 저걸 쓰는 편이

코드가 전체적으로 깔끔해보이는 효과고 있네요.