📩 출처
문제
크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.
'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.
레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.
아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.
7 . . . . . . . 7 . . . . . . .
6 . . . . . . C 6 . . . . . /-C
5 . . . . . . * 5 . . . . . | *
4 * * * * * . * 4 * * * * * | *
3 . . . . * . . 3 . . . . * | .
2 . . . . * . . 2 . . . . * | .
1 . C . . * . . 1 . C . . * | .
0 . . . . . . . 0 . \-------/ .
0 1 2 3 4 5 6 0 1 2 3 4 5 6입력
첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)
둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.
.: 빈 칸
*: 벽
C: 레이저로 연결해야 하는 칸
'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.
출력
첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.
👉 생각
- 거울을 배치해야 하는 곳은 탐색 하는 방향이 이전과 다르기 때문에 이러한 특징을 이용해서 q에서 체크를 해주어야 한다.
- q에 좌표와, 거울의 횟수, 방향 좌표를 넣어주고 너비우선 탐색을 돌린다. 여기서 방문 체크를 해주어야 하는데, 좀 다르게 생각을 해야 한다.
- 다른 좌표에서 이미 방문을 했다고 처리를 하면 최소 거울을 사용해야 하는 문제의 조건을 만족하지 못한다.
- 따라서 방문처리한 곳의 값을 거울의 개수로 두고, 또 다시 방문 하는 곳의 cnt를 현재 visited 값과 비교를 해서 cnt가 작은 경우에만 너비우선 탐색을 한다!
import sys
from collections import deque
input = sys.stdin.readline
big = sys.maxsize
def bfs(x, y):
q = deque([])
visited = [[big] * w for _ in range(h)]
q.append((x, y, 0, 0, 0))
visited[x][y] = 0
while q:
x, y, cnt, direction_x, direction_y = q.popleft()
if x == e1 and y == e2:
return cnt
if visited[x][y] < cnt:
continue
visited[x][y] = cnt
for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < h and 0 <= ny < w and arr[nx][ny] != '*':
if (direction_x == 0 and direction_y == 0) or (direction_x == dx and direction_y == dy):
q.appendleft((nx, ny, cnt, dx, dy))
else:
q.append((nx, ny, cnt+1, dx, dy))
w, h = map(int, input().split())
arr = [list(input().rstrip()) for _ in range(h)]
idx = []
for i in range(h):
for j in range(w):
if arr[i][j] == 'C':
idx.append((i, j))
if len(idx) == 2:
break
s1, s2 = idx[0]
e1, e2 = idx[1]
res = bfs(s1, s2)
print(res)
