[문제 바로가기] 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를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.
💡 문제 풀이
BFS 알고리즘으로 해결한 문제
최소 거리로 두 개의 'C'를 연결하는 것이 아닌, 최소 개수의 거울을 사용하는 것이 목표다.
거울을 사용한다는 것은 이전과 다른 방향으로 레이저가 이동할 때다.
따라서 탐색 중 visited(2차원 배열)에 입력하는 값은 해당 지점까지의 최소 거리가 아닌, 해당 지점까지 최소 개수의 거울을 사용한 값을 넣어준다.
방향전환에 따라 거울 사용 유무를 알 수 있기 때문에 큐(queue)에 4가지 원소를 묶어서 담았다. → (행, 열, 방향(상, 하, 좌, 우), 거울 사용 개수)
두 지점을 연결하기 위해 설치해야 하는 거울의 개수는 다양하게 나올 수 있기 때문에 두 지점 연결이 이루어질 때마다 res 변수에 최소값으로 업데이트한다.
코드는 다음과 같다.
import sys
from collections import deque
d = [(0, -1), (0, 1), (1, 0), (-1, 0)]
def bfs(i, j):
global W, H
queue = deque([])
visited = [[int(1e9)] * W for _ in range(H)]
visited[i][j] = 0
for idx in range(4):
r = i + d[idx][0]
c = j + d[idx][1]
if 0 <= r < H and 0 <= c < W and maps[r][c] == '.':
queue.append((r, c, idx, 0))
visited[r][c] = 0
res = int(1e9)
while queue:
r, c, dir, cnt = queue.popleft()
if maps[r][c] == 'C': # 두 지점 연결시
res = min(res, cnt) # 거울 개수의 최소값 업데이트
for idx in range(4):
nr = r + d[idx][0]
nc = c + d[idx][1]
if 0 <= nr < H and 0 <= nc < W:
if maps[nr][nc] != '*':
if idx == dir and cnt <= visited[nr][nc]: # 이전과 같은 방향일 경우
queue.append((nr, nc, dir, cnt))
visited[nr][nc] = min(visited[nr][nc], cnt)
elif idx != dir and cnt + 1 <= visited[nr][nc]: # 이전과 다른 방향일 경우
queue.append((nr, nc, idx, cnt + 1))
visited[nr][nc] = min(visited[nr][nc], cnt + 1)
return res
W, H = map(int, input().split())
maps = [''.join(map(str, sys.stdin.readline().rstrip())) for _ in range(H)]
points = []
is_Find = False
for r in range(H):
if is_Find: break
for c in range(W):
if maps[r][c] == 'C':
print(bfs(r, c)) # 처음 발견한 'C'를 시작점으로 선정 → BFS
is_Find = True
break
