[백준][Python][6087][BFS]레이저 통신

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

6087번: 레이저 통신

 

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)