6087 레이저 통신 파이썬

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

6087번: 레이저 통신

 

소스 코드

 

import sys
from collections import deque

W, H = map(int, sys.stdin.readline().split())
# H가 세로
mapp = [list(map(str, sys.stdin.readline().strip())) for _ in range(H)]

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
startx = starty = endx = endy = -1
for i in range(H):
    for j in range(W):
        if mapp[i][j] == 'C':
            if startx == -1:
                startx, starty = i, j
            else:
                endx, endy = i, j

visited = [[-1] * W for _ in range(H)]
q = deque()
q.append((startx, starty))
visited[startx][starty] = 0

while q:
    x, y = q.popleft()
    for k in range(4):
        nx, ny = x+dx[k], y+dy[k]
        while 0<= nx < H and 0<= ny < W:
            if mapp[nx][ny] == "*":
                break
            if visited[nx][ny] == -1:
                visited[nx][ny] = visited[x][y] + 1
                q.append((nx, ny))
            nx += dx[k]
            ny += dy[k]

print(visited[endx][endy] - 1)

 

어려워서 다른 분의 도움을 많이 받았음.

90도로 꺽이는 이동을 따로 계산한다는 건 가중치가 달라진다는 의미이다. 그렇게 하지 말고

가중치를 같은 1로 만들기 위한 방법이다.

거울을 설치한다는 것은 직선의 방향을 바꾸는 것

그래서 최소 직선의 개수 - 1 = 거울의 개수 이다.

 

소스 코드의 아이디어는 보통 bfs는 인접한 네 방향을 큐에 넣어서 진행시키는데

이 문제에서는 해당 방향의 정점들을 '*' 이라는 벽에 닿을 때까지 계속해서 큐에 넣는 것이다.

같은 직선상은 같은 그룹을 가지게 되고 가중치가 다 같은 상태에서 bfs를 할 수 있게 된다.