[백준/6087/파이썬] 레이저 통신

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

6087번: 레이저 통신

Problem

크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.

'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.

첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

조건

첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)

둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.

• .: 빈 칸
• *: 벽
• C: 레이저로 연결해야 하는 칸
• 'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.
• 레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.
• 아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.

SOL

쉬워보였지만, 엄청난 개념을 내포하고 있는 문제이다. 이런 문제 정말 좋다 :)

 

Trouble shooting! :)

• 거울이 설치되는 곳은, 내가 향하던 방향과 다른 방향으로 전환할 때, 거울이 설치되는 개념이다.
• 빛은 직진밖에 못하기 때문에, 아주 잘 와닿는 문제여서, 내가 향하는 방향을 deque에 저장해놓고, 내가 향하는 방향이랑, 지금 가려는 방향이 달라지면, mirror의 갯수를 +1을 해주는 개념으로 구현하였고, 코드도 잘 짜졌다.
• 하지만, 여기서 반례가 발생하였다. 

내가 원하는건, 형광펜 루트 였는데, dx,dy를 어떻게 설정하냐에 따라서, 맵이 어떻게 주어지냐 등등에 따라서,

edge(경로의 길이)가 같다면, 빨간색이든, 형광펜 둘 중에 먼저 도착하는 친구의 거울 갯수가 반영되는 오류가 나타난거다! 이 오류를 피해주기 위해서, visited[ny][nx]에 min(mirror,visited[ny][nx])를 해주면 된다고 생각했지만, 원래 작성했던 코드의 조건문을 넣어주는 흐름이 애매해져서, 다른 방법이 없을까 고민을 해봤다.

import sys
from collections import deque
input= sys.stdin.readline

M,N =map(int,input().split())
maps=[list(map(str,input().rstrip())) for _ in range(N)]
visited=[[0 for _ in range(M)] for _ in range(N)]
CtoC=[]
dx=[0,1,0,-1]
dy=[1,0,-1,0]
ans=sys.maxsize
for i in range(N):
    for j in range(M):
        if maps[i][j] =="C":
            CtoC.append((i,j))
            maps[i][j]="."
print(CtoC)
def bfs(y,x,dir,mirror):
    global ans
    dq=deque()
    dq.append((y,x,dir,mirror))
    visited[y][x] = 1
    while dq:
        y,x,dir,mirror=dq.popleft()
        print("y:{},x:{},dir:{},mirror:{}".format(y,x,dir,mirror))
        #if y==CtoC[1][0] and x==CtoC[1][1]:
            #ans=min(ans,mirror)
            #continue
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if not (0<=ny<N and 0<=nx<M):
                continue
            #이 코드를 어디에 넣을까..?
            #if ny==CtoC[1][0] and nx==CtoC[1][1]:
                #visited[ny][nx]=min(visited[ny][nx],mirror)
                #continue
            if maps[ny][nx]=="." and not visited[ny][nx]:
                if dir ==-1:
                    dq.append((ny,nx,k,mirror))
                    visited[ny][nx]=visited[y][x]+1
                    continue
                if  dir !=k:
                    dq.append((ny,nx,k,mirror+1))
                    visited[ny][nx] = visited[y][x]+1
                elif dir==k:
                    dq.append((ny,nx,k,mirror))
                    visited[ny][nx] = visited[y][x]+1

bfs(CtoC[0][0],CtoC[0][1],-1,0)
print(visited[CtoC[1][0]][CtoC[1][1]])

문제 해결한 코드 

• 빛이 직진하는것처럼, 시작점에서 한 방향으로 쭉 탐색해주는 BFS를 작성해보자! 이때, 방향이 꺽이면 , 거울의 갯수를 +1 해준다. 
• bfs문안에 while True를 활용하는 문제! 코드를 보면 쉽게 이해갈거다!

from collections import deque
import sys
input= sys.stdin.readline

M,N=map(int,input().split())
visited=[[float('inf') for _ in range(M)] for _ in range(N)]
maps=[input().rstrip() for _ in range(N)]
dx=[0,1,0,-1]
dy=[1,0,-1,0]
CtoC=[]
def bfs(y,x):
    dq=deque()
    dq.append((y,x))
    visited[y][x] =0
    while dq:
        y,x=dq.popleft()
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            while True:
                if not (0<=ny<N and 0<=nx<M):
                    break
                if maps[ny][nx] =="*":
                    break
                # 방문을 했는데, 거울의 갯수가 더 많으면, break
                if visited[ny][nx] < visited[y][x] +1:
                    break
                dq.append((ny,nx))
                visited[ny][nx]=visited[y][x] +1
                ny+=dy[k]
                nx+=dx[k]

for i in range(N):
    for j in range(M):
        if maps[i][j] =="C":
            CtoC.append((i,j))
            
sy,sx=CtoC[0]
ey,ex=CtoC[1]
bfs(sy,sx)
print(visited[ey][ex]-1)