BOJ 6087 레이저 통신

백준 6087 링크

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

풀이

각 칸마다 최소 몇번의 거울을 써서 이동했나를 저장해 가면서 다익스트라로 풀었습니다.

 

그냥 큐로 푼사람도 있던데 조금 더 생각을 해봐야 할 것 같은...

 

특이한 점은 같은 회수의 거울을 이용 하더라도 온 방향이 다를 경우엔 답이 달라질 수 있으므로

저장된 최소 비용 >= 현재비용

으로 비교를 하였습니다.

 

조금 더 생각해본 결과 레이저 처럼 쭉쭉 뻗어나간다는 생각을 도입해보면 큐를 이용할 수 있다고 생각하여 다시 구현해보았습니다.

 

큐를 이용한 방법을 쓰니까 조금 더 빠르네요

코드

#다익스트라
import heapq
input = __import__('sys').stdin.readline
m,n = map(int, input().split())
mp = [input() for _ in range(n)]
visit = [[float("inf")] * m for _ in range(n)]
check = 0
sy = sx = ey = ex = -1
ly,lx = [1,-1,0,0],[0,0,-1,1]
for i in range(n):
    for j in range(m):
        if mp[i][j] == 'C' and check == 0:
            sy,sx = i,j
            check+=1
        elif mp[i][j] == 'C':
            ey,ex = i,j
            break
#0,1,2,3 하상좌우
#들어가는 데이터는 (꺾은 회수,현재 방향,y,x)
ans = float("inf")
visit[sy][sx] = 0
q = []
heapq.heappush(q,(0,0,sy,sx))
heapq.heappush(q,(0,1,sy,sx))
heapq.heappush(q,(0,2,sy,sx))
heapq.heappush(q,(0,3,sy,sx))
while q:
    turned,nowdir,y,x = heapq.heappop(q)
    if y == ey and x == ex:
        ans = min(turned,ans)
    else:
        for i in range(4):
            ny,nx = y + ly[i],x + lx[i]
            if 0 <= ny < n and 0 <= nx < m and mp[ny][nx] != '*':
                if i != nowdir and visit[ny][nx] >= turned + 1:
                    visit[ny][nx] = turned + 1
                    heapq.heappush(q,(turned + 1,i,ny,nx))
                elif i == nowdir and visit[ny][nx] >= turned:
                    visit[ny][nx] = turned
                    heapq.heappush(q,(turned,nowdir,ny,nx))
print(ans)

#BFS
import queue
input = __import__('sys').stdin.readline
m,n = map(int, input().split())
mp = [input() for _ in range(n)]
visit = [[float("inf")] * m for _ in range(n)]
check = 0
sy = sx = ey = ex = -1
ly,lx = [1,-1,0,0],[0,0,-1,1]
for i in range(n):
    for j in range(m):
        if mp[i][j] == 'C' and check == 0:
            sy,sx = i,j
            check+=1
        elif mp[i][j] == 'C':
            ey,ex = i,j
            break
visit[sy][sx] = 0
q = queue.Queue()
q.put((sy,sx))
while q.empty()==False:
    y,x=q.get()
    for i in range(4):
        ny,nx=y+ly[i],x+lx[i]
        while True:
            if 0<=ny<n and 0<=nx<m and mp[ny][nx]!='*' and visit[ny][nx]>=visit[y][x]+1:
                q.put((ny,nx))
                visit[ny][nx]=visit[y][x]+1
            else:
                break
            ny,nx=ny+ly[i],nx+lx[i]
print(visit[ey][ex]-1)