취준/백준
[백준][Python][6087][BFS]레이저 통신
puff
2020. 2. 23. 12:45
문제 : https://www.acmicpc.net/problem/6087
6087번: 레이저 통신
문제 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다. 레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.
www.acmicpc.net
BFS 문제다.
이 문제는 큐에 좌표값만이 아닌, 현재의 방향과 꺾은 횟수를 같이 넣어줘야 한다.
그리고, 방향을 돌릴 때, 현재 방향과 다르면 +1을 해주고 큐에 넣는다.
이 때, 맵에 방문 기록을 해야되는데, 단순한 True/False 가 아닌, 현재까지 방문한 것들 중에서 가장 작은 횟수만큼 꺾은 값을 방문 기록에 넣어줘야 한다.
import sys
from collections import deque
w,h = [int(i) for i in sys.stdin.readline().split()]
d = []
visited = [[912341234 for _ in range(w)] for _ in range(h)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
for _ in range(h):
d.append([i for i in sys.stdin.readline().rstrip()])
laser = []
for i in range(h):
for j in range(w):
if d[i][j] =='C':
laser.append([i,j])
q = deque()
#laser y, laser x, direction 0 , curved num
q.append(laser[0] + [0,0])
q.append(laser[0] + [1,0])
q.append(laser[0] + [2,0])
q.append(laser[0] + [3,0])
ret = 912341234
visited[laser[0][0]][laser[0][1]] = 0
while q:
cur = q.popleft()
if cur[0:2] ==laser[1]:
ret = min(ret,cur[3])
for i in range(4):
ny,nx = cur[0] + dy[i], cur[1]+dx[i]
ncount = cur[3]
if 0>ny or ny>=h or 0>nx or nx>=w:
continue
if d[ny][nx] =="*":
continue
if cur[2] != i:
ncount+=1
if visited[ny][nx] >= ncount:
visited[ny][nx] = ncount
q.append([ny,nx,i, ncount])
print(ret)