백준 6087 : 레이저 통신 (Python)

본문 링크

import sys,heapq
input=sys.stdin.readline
dx=[-1,1,0,0]
dy=[0,0,-1,1]

def Dijkstra():

    dp=[ [INF]*(M+1) for _ in range(N+1) ]
    dp[start[0][0]][start[0][1]]=0
    heap=[]
    heapq.heappush(heap,(0 , start[0][0] , start[0][1] , 0)) #방향을 잡는다.
    heapq.heappush(heap,(0 , start[0][0] , start[0][1] , 1)) #방향을 잡는다.
    heapq.heappush(heap,(0 , start[0][0] , start[0][1] , 2)) #방향을 잡는다.
    heapq.heappush(heap,(0 , start[0][0] , start[0][1] , 3)) #방향을 잡는다.

    graph[start[0][0]][start[0][1]]="*"

    while heap:

        value,x,y,direction=heapq.heappop(heap)

        if graph[x][y]=="C":

            return value

        if dp[x][y]<value:
            continue


        for i in range(4):

            nx=x+dx[i] ; ny=y+dy[i]

            if 0<=nx<N and 0<=ny<M and graph[nx][ny]!="*":

                if direction==i and value<=dp[nx][ny]:
                    dp[nx][ny]=value
                    heapq.heappush(heap,(value , nx , ny , direction))


                elif direction!=i and value+1<=dp[nx][ny]:
                    dp[nx][ny]=value+1
                    heapq.heappush(heap,(value+1,nx,ny,i))





INF=int(1e9)

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

graph=[ list(input().rstrip()) for _ in range(N) ]
start=[]

for i in range(N):
    for j in range(M):
        if graph[i][j]=="C":
            start.append([i,j])

print( Dijkstra() )

📌 어떻게 접근할 것인가?

다익스트라를 이용해 구했습니다. 상하좌우로 이동했을때의 정보를 담아서 다음번에 상하좌우로 이동할때 이전에 이동했던 방향과 일치하다면 그냥 이동하고 그렇지 않으면 값을 +1 추가해서 이동해줍니다.

이때 이동가능한 모든 경로를 찾아야 하기 때문에

• if direction==i and value<dp[nx][ny]:
• if direction==i and value<=dp[nx][ny]:

조건문에서 비록 다음번에 이동할 위치에 값이 변화가 없더라도 꼭 이동해주어야 합니다.
따라서 아래 조건문으로 탐색해야합니다. 왜냐하면 같은 최단경로를 이동했을 지라도 방향이 다를수 있기 때문입니다.

이후 그래프의 값이 C 라면 return 을 해주고 함수를 종료시킵니다.