[백준 6987번] 레이저 통신(파이썬)

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

6087번: 레이저 통신

이 문제의 입력은

무조건 C와 C가 서로 연결되는 구조라는 가정이 있습니다.

이 문제는 거울을 어떻게 넣어줄건지 생각하면 되는 문제입니다.

다익스트라로 풀 수 있는데

한가지 주의할 포인트가 있습니다.

(.은 0

*은 1

출발점은 f

도착점은 e)

이 그림의 □의 경우에는

여러 방향에서 오는 케이스가 존재합니다.

다익스트라 알고리즘을 쓰다가

이 부분을 놓쳐서 다소 해맸다가 수정했습니다.

#백준 6087번 레이저통신
from heapq import heappop,heappush
dx=[0,1,0,-1]
dy=[-1,0,1,0]

W,H=map(int,input().split())
fx=-1
fy=-1
ex=-1
ey=-1

room=[[0]*W for _ in range(H)]
mirror=[[1e9]*W for _ in range(H)]
for i in range(H):
    tmp=input().rstrip()
    for j in range(W):
        if tmp[j]=='.':
            room[i][j]=0
        elif tmp[j]=='*':
            room[i][j]=1
        elif tmp[j]=='C':
            if fx==-1 and fy==-1:
                fx=i
                fy=j
                room[i][j]=0
            else:
                ex=i
                ey=j
                room[i][j]=2

mirror[fx][fy]=0
heap=[]

heappush(heap,[0,fx,fy,0])
heappush(heap,[0,fx,fy,1])
heappush(heap,[0,fx,fy,2])
heappush(heap,[0,fx,fy,3])
while heap:
    cnt,x,y,ro=heappop(heap)
    if x==ex and y==ey:
        continue
    if cnt>mirror[x][y]:
        continue
    for d in range(4):
        nx=x+dx[d]
        ny=y+dy[d]
        if nx<0 or nx>=H or ny<0 or ny>=W:
            continue
        if room[nx][ny]==1:
            continue
        #같은 방향
        if ro==d:
            if mirror[nx][ny]>=cnt:
                #등호를 붙인 이유:다른 방향에서 들어오는 경우를 가정
                mirror[nx][ny]=cnt
                heappush(heap,[cnt,nx,ny,d])
        #방향 틀떄
        elif (ro+1)%4==d:
            if mirror[nx][ny]>=cnt+1:
                #등호를 붙인 이유:다른 방향에서 들어오는 경우를 가정
                mirror[nx][ny]=cnt+1
                heappush(heap,[cnt+1,nx,ny,d])
        #방향 틀때
        elif (ro-1)%4==d:
            if mirror[nx][ny]>=cnt+1:
                #등호를 붙인 이유:다른 방향에서 들어오는 경우를 가정
                mirror[nx][ny]=cnt+1
                heappush(heap,[cnt+1,nx,ny,d])


print(mirror[ex][ey])

방향설정할 때,

90도로 회전하도록 설정해주는 것도 잊지말아주세요.

https://bingorithm.tistory.com/2

"백준 6087번-레이저 통신" 반례 모음

여기에 수 많은 반례케이스가 있습니다.

반례를 보면서 코드의 틀린 부분을 수정해보셔도 좋습니다.