[백준 6087] 레이저 통신(Python)

1. 요약

2개의 레이저간의 통신을 하려고한다.(항상 통신이 가능하다고 간주한다.)

레이저는 벽을 뚫을 수 없으며, 빈칸을 통행 움직인다. 레이저는 특성상 직진하며, 거울을 설치해서 방향을 90도로 회전시켜 바꿀 수 있다. 설치에 필요한 거울의 최소 개수를 구하는 것이 우리가 풀어야할 문제이다.

2. 아이디어

BFS로 문제를 해결한다.

*이 아닌 칸에 대하여, 필요한 거울의 최솟값을 기록한다.

거울의 설치 여부는 이전의 좌표 값과 다음의 좌표를 비교하는 것이다.(abs(py-ny) == abs(px-nx))

거울의 최솟값을 table[ny][nx]에 기록하기 위해, 조건을 세워서 table[ny][nx]에 값을 갱신하고 거울의 개수, 다음좌표, 현재좌표를 큐에 넣는다.

수직의 여부를 고려해서 조건을 세웠다.

수직일 때, if table[ny][nx] >= cnt +1: table[ny][nx] = cnt+1, 큐에 위에 언급된 정보 삽입

수직이 아닐 때, if table[ny][nx] >= cnt: table[ny][nx] = cnt, 큐에 위에 언급된 정보 삽입

여기서 >가 아닌 >=을 붙인 이유는 이전의 좌표도 고려해야하기 때문이다.

예를 들어 4x4 지도가 아래와 같다고 할 때 4번 째 줄 C 바로 왼쪽에 있는 .을 살펴보자

C..*
....
...*
...C

여기서 출발 했던 곳이 바로 왼쪽이거나 바로 위쪽이더라도 필요한 거울의 최솟값은 2로 같다. 하지만 오른쪽으로 있는 C로 갈 때, 왼쪽에서 출발했던 곳은 그대로 2지만, 위쪽에서 출발 했던 곳은 3이 되어서 값의 차이가 난다. 따라서 이러한 상황을 고려해야하므로 >=를 붙였다.

3. 코드

import sys
from collections import deque

c, r = map(int, sys.stdin.readline().rstrip().split())
src = [-1, -1]
dst = [-1, -1]
arr = []
d = [[0,1], [0,-1], [1,0], [-1,0]]

for i in range(r):
    x = list(sys.stdin.readline().rstrip())
    arr.append(x)

    for j in range(c):
        if x[j] == 'C':
            if src == [-1, -1]: src[0], src[1] = i, j
            else: dst[0], dst[1] = i, j

def isin(y,x):
    if -1<y<r:
        if -1<x<c: return True
    return False

def is_right_angle(py, px, ny, nx):
    return abs(py-ny) == abs(px-nx)

def solve():
    visited = [[False for _ in range(c)] for _ in range(r)]
    sy, sx = src[0], src[1]
    q = deque()
    q.append([0, sy, sx, sy, sx])
    visited[sy][sx] = True
    table = [[0 for _ in range(c)] for _ in range(r)]

    while q:
        cnt, y, x, py, px = q.popleft()

        for i in range(4):
            ny = y + d[i][0]
            nx = x + d[i][1]

            if isin(ny, nx):
                if not visited[ny][nx]:
                    visited[ny][nx] = True
                    if arr[ny][nx] != '*':
                        if is_right_angle(py, px, ny, nx):
                            table[ny][nx] = cnt + 1                  
                            q.append([cnt+1, ny, nx, y, x])
                        
                        else:
                            table[ny][nx] = cnt 
                            q.append([cnt, ny, nx, y, x])
                
                elif is_right_angle(py, px, ny, nx):
                    if table[ny][nx] >= cnt + 1:
                        table[ny][nx] = cnt + 1
                        q.append([cnt+1, ny, nx, y, x])
                
                elif table[ny][nx] >= cnt:
                    table[ny][nx] = cnt
                    q.append([cnt, ny, nx, y, x])
    
    print(table[dst[0]][dst[1]])

solve()