BOJ (레이저통신) 6087

작성일 | In

레이저 통신

  • 크기가 WxH인 지도가 주어졌을 때

  • 두 C를 레이저로 연결하기 위해서 설치해야 하는 거울 개수의 최소값을 구하는 문제

  • 레이저를 쏘고 싶을 때, 그 때 거울이 몇개 필요한지 구하는 문제
  • 레이저 통신 문제는 쭉 이동할 수가 있다.
  • 이 때, 몇번 꺾는 지를 구하는 문제. 일반적인 연산이 아니다.
  • 어떤 칸에서 이동할 수 있는 정점은 인접한 네 칸이 아니고 쭉 이라는 거다. 거울이라고 생각하지말고 거리라고 생각해보자.
  • 이동 경로가 바뀌면 거울이 필요
  • 즉 직선의 개수를 구해주고 거기서 -1을 해주면 된다.
  • 한번에 이동할 수 있는 방향을 한번에 큐에 넣는거다.

  • 결국 (sx,sy) 에서 (ex,ey)로 가는 최단거리를 구하는 문제

  • 직선의 개수는 하나씩 늘어나니까 bfs가 맞다.
  • while문을 추가해줘서 그 방향이 벽이 아니면 계속 진행하게 만들어준다.
from collections import deque
dx = [0,0,1,-1]
dy = [1,-1,0,0]
m,n = map(int,input().split())
a = [input() for _ in range(n)]
sx=sy=ex=ey=-1
for i in range(n):
    for j in range(m):
        if a[i][j] == 'C':
            if sx == -1:
                sx,sy = i,j
            else:
                ex,ey = i,j
dist = [[-1]*m for _ in range(n)]
q = deque()
dist[sx][sy] = 0
q.append((sx,sy))
while q:
    x,y = q.popleft()
    for k in range(4):
        nx,ny = x+dx[k],y+dy[k]
        while 0 <= nx < n and 0 <= ny < m:
            if a[nx][ny] == '*':
                break
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx,ny))
            nx += dx[k]
            ny += dy[k]
print(dist[ex][ey]-1)

참고자료 codeplus

0%