문제
[문제]
채영이는 거울을 들여다보는 것을 참 좋아한다. 그래서 집 곳곳에 거울을 설치해두고 집 안을 돌아다닐 때마다 거울을 보곤 한다.
채영이는 새 해를 맞이하여 이사를 하게 되었는데, 거울을 좋아하는 그녀의 성격 때문에 새 집에도 거울을 매달만한 위치가 여러 곳 있다.
또한 채영이네 새 집에는 문이 두 개 있는데, 채영이는 거울을 잘 설치하여 장난을 치고 싶어졌다.
즉, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 거울을 설치하고 싶어졌다.
채영이네 집에 대한 정보가 주어졌을 때,
한 쪽 문에서 다른 쪽 문을 볼 수 있도록 하기 위해 설치해야 하는 거울의 최소 개수를 구하는 프로그램을 작성하시오.
거울을 설치할 때에는 45도 기울어진 대각선 방향으로 설치해야 한다.
또한 모든 거울은 양면 거울이기 때문에 양 쪽 모두에서 반사가 일어날 수 있다.
채영이는 거울을 매우 많이 가지고 있어서 거울이 부족한 경우는 없다고 하자.
거울을 어떻게 설치해도 한 쪽 문에서 다른 쪽 문을 볼 수 없는 경우는 주어지지 않는다.
[입력]
첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다.
다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다.
- ‘#’는 문이 설치된 곳으로 항상 두 곳이며,
- ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다.
- ‘!’은 거울을 설치할 수 있는 위치를 나타내고,
- ‘*’은 빛이 통과할 수 없는 벽을 나타낸다.
[출력]
첫째 줄에 설치해야 할 거울의 최소 개수를 출력한다.아이디어
문제 상황 설명
- 한쪽 문에서 레이저를 발사했을 때, 거울을 최소로 설치해서 다른 한쪽 문으로 레이저가 나갈 수 있도록 하면 된다.
0-1 BFS
-
그래프에서 간선의 가중치가 0 or 1일 때 사용할 수 있는 풀이 기법
-
이번 문제에서 '!' 칸에 도달하면 거울을 설치하거나, 설치하지 않을 수 있다.
- 거울을 설치하는 경우 -> 가중치 1
- 거울을 설치하지 않는 경우 -> 가중치 0
-
가중치가 0인 경우는 큐의 앞에 삽입하고, 가중치가 1인 경우는 큐의 뒤에 삽입해서 도착점에 도달했을 때, 거울을 설치한 개수가 최소가 되도록 한다.
제출 코드
Python
import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
arr = [list(input().rstrip()) for _ in range(n)]
# 시작점
start = (-1, -1)
for r in range(n):
stop = False
for c in range(n):
if arr[r][c] == '#':
start = (r, c)
stop = True
break
if stop:
break
# 방향: 상,하,좌,우
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
# visited[r][c][i]: (r, c)에 i방향으로 진입한 적이 있는지 체크
visited = [[[False] * 4 for _ in range(n)] for __ in range(n)]
q = deque([])
for i in range(4):
visited[start[0]][start[1]][i] = True
q.append((start[0], start[1], i, 0)) # (r, c, 방향, 가중치)
# 0-1 BFS
# 거울을 설치하는 경우 가중치 + 1 -> 큐의 뒤에 삽입
# 거울을 설치하지 않는 경우 가중치 + 0 -> 큐의 앞에 삽입
ans = float('inf')
while q:
r, c, dir, wt = q.popleft()
# 도착점에 도달한 경우
if arr[r][c] == '#' and (r != start[0] or c != start[1]):
ans = wt
# 0-1 BFS로 풀었으므로 처음 나온 답이 최소 거울 개수
break
# 빛은 거울과 만나지 않는 이상 이전 진행 방향을 유지하며 직진한다.
nr = r + dr[dir]
nc = c + dc[dir]
# 범위 밖
if nr < 0 or nr >= n or nc < 0 or nc >= n:
continue
# 방문
if visited[nr][nc][dir]:
continue
# [1] 벽
if arr[nr][nc] == '*':
continue
# [2] 거울
if arr[nr][nc] == '!':
visited[nr][nc][dir] = True
# (1) 거울을 설치하는 경우
# 0-1 BFS: 거울을 설치하는 경우 큐 뒤에 삽입
# 기존 진행 방향 상/하 -> 좌/우 빛 반사 가능
if dir == 0 or dir == 1:
q.append((nr, nc, 2, wt + 1))
q.append((nr, nc, 3, wt + 1))
# 기존 진행 방향 좌/우 -> 상/하 빛 반사 가능
else:
q.append((nr, nc, 0, wt + 1))
q.append((nr, nc, 1, wt + 1))
# (2) 거울을 설치하지 않는 경우
q.appendleft((nr, nc, dir, wt))
# [3] 빛이 통과할 수 있는 곳 (빈칸/도착점 문)
else:
visited[nr][nc][dir] = True
q.appendleft((nr, nc, dir, wt))
print(ans)참고 사이트
코뉴로그