[백준/Python] 6087번 - 레이저 통신

문제

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

 

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

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

레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.

아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.

 

 

 

 

입력

 

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

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

• .: 빈 칸
• *: 벽
• C: 레이저로 연결해야 하는 칸

'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.

 

 

출력

 

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

 

 

 

풀이

 

처음에는 거울을 설치해 방향을 오른쪽, 왼쪽으로 바꾸거나 앞으로 가는 3가지 경우를 고려해 BFS로 문제를 풀었다. 문제는 BFS로 풀었더니 정답은 맞지만 시간초과가 떠서 같은 지점을 지날 경우 최소값을 고려해 최소값이 아닌 노드를 삭제하며 풀이를 했지만 마찬가지로 시간초과가 떴다.

그래서 다른방법으로 문제를 풀었는데, 레이저는 벽을 만나거나 거울을 만나기 전에는 계속 이동한다는 점을 이용했다. queue에서 pop한 좌표를 기준으로 벽을 만나기 전까지 모든 지점을 범위로 지정하고, 그 지점이 방문을 한 적이 없다면 지금까지 거울을 만난 횟수를 저장하고 queue에 append했다. 만약 이미 방문했다면, 그냥 pass했다(이미 방문했다면 최솟값이 저장됐기 때문에 비교할 필요가 없기 때문에 pass).

그리고 만약 C에 도달했다면 그때 횟수를 출력하면 정답이 된다.

 

 

Code

 

 

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

W,H=map(int,input().split())
lst=tuple(list(input()) for _ in range(H))
visit=tuple([0]*W for _ in range(H))
dv=((-1,0),(1,0),(0,-1),(0,1)) #상하좌우 0123
dv_dic={0:(0,2,3),1:(1,2,3),2:(0,1,2),3:(0,1,3),4:(0,1,2,3)} #이전 이동방향에 따라 현재 어디로 방향을 바꿀 수 있는지를 dictionary로 저장
C_rot=[]
for Y in range(H):
        for X in range(W):
            if lst[Y][X]=='C':
                C_rot.append((Y,X))
y,x=C_rot[0]
min_n=10000
queue=deque()
queue.append((y,x,4,0)) # 0은 방문 구분, chg=거울개수+1개를 의미, 4번은 초기화
visit[y][x]=1 #첫 시작점은 1로 초기화
while queue:
    y,x,dir,chg=queue.popleft()
    if (y,x)==C_rot[1]:
        min_n=min(min_n,chg)
        break
    for i in dv_dic[dir]:
        a=chg
        dy=y+dv[i][0]
        dx=x+dv[i][1]
        if dir!=i: #만약 방향을 바꾼다면 거울 +1
            a+=1
        while True:
            if 0<=dy<H and 0<=dx<W and lst[dy][dx]!='*': # 벽이 아니거나 dy, dx가 범위 이내라면 
                if not visit[dy][dx]: # 방문한 적이 없다면
                    visit[dy][dx]=a  # 현재 만난 거울의 수를 저장 
                    queue.append((dy,dx,i,a))
                dy+=dv[i][0] #레이저이므로 쭉 직진
                dx+=dv[i][1]
            else:
                break
print(min_n-1)

 

---

 

 

BFS를 쓰면 완전탐색을 할 수 있지만, 시간이 오래걸릴 수 있기 때문에 문제를 풀때 중복을 줄일 방법을 더 생각해 봐야겠다