알고리즘/[Python] 백준
(Python) 백준 6087번 : 레이저 통신
maengjh
2020. 2. 16. 18:43
출처 : https://www.acmicpc.net/problem/6087
6087번: 레이저 통신
문제 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다. 레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.
www.acmicpc.net
In [1]:
from collections import deque
In [2]:
def bfs(x,y):
queue = deque([(x,y)])
visited[x][y] = 0
while queue:
x,y = queue.popleft()
for i in range(4):
## 동 남 서 북 순서
nx, ny = x+dx[i], y+dy[i]
while True:
## 범위를 벗어난다
if not(0<=nx<n and 0<=ny<m): break
## 벽을 만난다
if board[nx][ny]=='*': break
## 지난 적 있는 곳인데, 지금 경로로는 너무 많은 거울이 필요해서 break
if visited[nx][ny] < visited[x][y]+1: break
## board업데이트, queue 추가
queue.append((nx,ny))
visited[nx][ny] = visited[x][y] + 1
nx = nx+dx[i]
ny = ny+dy[i]
In [3]:
if __name__=='__main__':
## 입력값
m,n = map(int, input().split())
board = [input() for _ in range(n)]
## 동 남 서 북
dx = (0,1,0,-1)
dy = (1,0,-1,0)
## C위치
C = []
for i in range(n):
for j in range(m):
if board[i][j] == 'C':
C.append((i,j))
## sx,sy : 시작지점
## ex,ey : 도착지점
(sx,sy), (ex,ey) = C
visited = [[float('inf')]*m for _ in range(n)]
bfs(sx,sy)
print(visited[ex][ey]-1)