💡 문제
채영이는 거울을 들여다보는 것을 참 좋아한다. 그래서 집 곳곳에 거울을 설치해두고 집 안을 돌아다닐 때마다 거울을 보곤 한다.
채영이는 새 해를 맞이하여 이사를 하게 되었는데, 거울을 좋아하는 그녀의 성격 때문에 새 집에도 거울을 매달만한 위치가 여러 곳 있다. 또한 채영이네 새 집에는 문이 두 개 있는데, 채영이는 거울을 잘 설치하여 장난을 치고 싶어졌다. 즉, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 거울을 설치하고 싶어졌다.
채영이네 집에 대한 정보가 주어졌을 때, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 하기 위해 설치해야 하는 거울의 최소 개수를 구하는 프로그램을 작성하시오.
거울을 설치할 때에는 45도 기울어진 대각선 방향으로 설치해야 한다. 또한 모든 거울은 양면 거울이기 때문에 양 쪽 모두에서 반사가 일어날 수 있다. 채영이는 거울을 매우 많이 가지고 있어서 거울이 부족한 경우는 없다고 하자.
거울을 어떻게 설치해도 한 쪽 문에서 다른 쪽 문을 볼 수 없는 경우는 주어지지 않는다.
입력
첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. #는 문이 설치된 곳으로 항상 두 곳이며, .은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. !은 거울을 설치할 수 있는 위치를 나타내고, *은 빛이 통과할 수 없는 벽을 나타낸다.
출력
첫째 줄에 설치해야 할 거울의 최소 개수를 출력한다.
💭 접근
이 문제를 처음 풀었을 때 다익스트라와 비슷한 방식으로 나아가며 현재까지 설치한 거울의 개수를 저장하고, 개수가 적을 때만 동일한 칸을 다시 방문 할 수 있도록 구현하였지만 메모리초과가 발생하였다.
따라서 따로 방문 체크를 하지않고 단순히 거울을 최대한 설치하지 않는 방향으로 나아가고, BFS를 사용하여 가장 먼저 도착할 때 최적해를 구할 수 있도록 구현하였다.
- 먼저 시작 지점에서 나아갈 수 있는 모든 방향을 탐색한다.
ans = float('inf')
for i in range(4):
nx = start_x + dx[i]
ny = start_y + dy[i]
if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] != '*':
start_dir = i
bfs(start_x, start_y, start_dir, 0)- 빛의 특성 상, 벽이나 거울을 만나지 않는 한 계속해서 앞으로 나아가므로 벽과 거울을 만날 때까지 현재 방향을 유지하며 나아간다.
while q:
x, y, dir, cnt = q.popleft()
mirror = False
while True:
if x == end_x and y == end_y:
ans = min(ans, cnt)
return
x += dx[dir]
y += dy[dir]
if 0 <= x < n and 0 <= y < n:
if graph[x][y] == '*':
break
if graph[x][y] == '!':
mirror = True
break
else:
break- 만약 거울을 만났다면 다음으로 나아갈 수 있는 방향을 정한다.
if mirror:
if dir == 0: back = 1
elif dir == 1: back = 0
elif dir == 2: back = 3
elif dir == 3: back = 2
for i in range(4):
if i != back:
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] != '*':
if i == dir:
q.appendleft([x, y, i, cnt])
else:
q.append([x, y, i, cnt + 1])거울을 만났을 때 빛이 나아갈 수 있는 방향은 현재방향유지(거울 설치 X) 또는 거울을 설치하여 굴절되는 방향이며, 다시 반대로 반사될 수 없다.
이때, 설치한 거울의 최소를 구해야 하므로 거울을 설치하지 않고 현재 방향을 유지하며 나아가는 것을 우선적으로 탐색한다.
📒 코드
from collections import deque
def bfs(x, y, dir, cnt):
global ans
q = deque()
q.append([x, y, dir, cnt])
while q:
x, y, dir, cnt = q.popleft()
mirror = False
while True:
if x == end_x and y == end_y:
ans = min(ans, cnt)
return
x += dx[dir]
y += dy[dir]
if 0 <= x < n and 0 <= y < n:
if graph[x][y] == '*':
break
if graph[x][y] == '!':
mirror = True
break
else:
break
if mirror:
if dir == 0: back = 1
elif dir == 1: back = 0
elif dir == 2: back = 3
elif dir == 3: back = 2
for i in range(4):
if i != back:
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] != '*':
if i == dir:
q.appendleft([x, y, i, cnt])
else:
q.append([x, y, i, cnt + 1])
n = int(input())
graph = [list(input()) for _ in range(n)]
door = []
for i in range(n):
for j in range(n):
if graph[i][j] == '#':
door.append([i, j])
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
start_x, start_y = door[0]
end_x, end_y = door[1]
ans = float('inf')
for i in range(4):
nx = start_x + dx[i]
ny = start_y + dy[i]
if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] != '*':
start_dir = i
bfs(start_x, start_y, start_dir, 0)
print(ans)💭 후기
BFS 문제를 풀며 방문처리를 하지 않는 경우가 드물기에 풀이 방법을 떠올리는 것이 까다로웠던 문제였다.
🔗 문제 출처
https://www.acmicpc.net/problem/2151
