문제 바로가기
문제:
채영이는 거울을 들여다보는 것을 참 좋아한다. 그래서 집 곳곳에 거울을 설치해두고 집 안을 돌아다닐 때마다 거울을 보곤 한다. 채영이는 새 해를 맞이하여 이사를 하게 되었는데, 거울을 좋아하는 그녀의 성격 때문에 새 집에도 거울을 매달만한 위치가 여러 곳 있다. 또한 채영이네 새 집에는 문이 두 개 있는데, 채영이는 거울을 잘 설치하여 장난을 치고 싶어졌다. 즉, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 거울을 설치하고 싶어졌다. 채영이네 집에 대한 정보가 주어졌을 때, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 하기 위해 설치해야 하는 거울의 최소 개수를 구하는 프로그램을 작성하시오. 거울을 설치할 때에는 45도 기울어진 대각선 방향으로 설치해야 한다. 또한 모든 거울은 양면 거울이기 때문에 양 쪽 모두에서 반사가 일어날 수 있다. 채영이는 거울을 매우 많이 가지고 있어서 거울이 부족한 경우는 없다고 하자. 거울을 어떻게 설치해도 한 쪽 문에서 다른 쪽 문을 볼 수 없는 경우는 주어지지 않는다.
입력:
첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다.
출력:
첫째 줄에 설치해야 할 거울의 최소 개수를 출력한다.
풀이:
bfs 로 풀었다.
각 좌표마다 들어오는 빛의 방향마다 해준다. 빛은 4방향으로 들어온다 위 아래 왼쪽 오른쪽
거울을 만나면 90도 방향으로 꺾여서 날라가게된다.
import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
# 4개의 방향에서 빛이 날라옴, 각좌표마다 날라오는 빛의 방향마다 가져야함. 3차원?
# 각 좌표 마다의 도착하는 빛의 방향 별로 거울 갯수 필요 최신화
# 다익스? 굳이? 최단거리니까
N = int(input())
graph = [list(map(str, input())) for _ in range(N)]
mirrors = []
move = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 방향 순서 오른쪽 아래 왼쪽 위
for x in range(N):
for y in range(N):
if graph[x][y] == "#":
mirrors.append((x, y))
# 시작
sx, sy = mirrors[0]
graph[sx][sy] = "Start"
def bfs(sx, sy):
Q = deque()
visited = [[[0 for _ in range(4)] for _ in range(N)] for _ in range(N)]
for direction in range(4):
Q.append((sx, sy, direction))
visited[sx][sy][direction] = 1
while Q:
current_x, current_y, current_direction = Q.popleft()
dx, dy = move[current_direction]
nx, ny = current_x, current_y
while True:
nx = nx + dx
ny = ny + dy
# print(current_x, current_y, nx, ny,Q)
if not (0 <= nx < N and 0 <= ny < N) or graph[nx][ny] == "*":
break
if graph[nx][ny] == "!":
# 가던 방향
if not visited[nx][ny][current_direction]:
Q.append((nx, ny, current_direction))
visited[nx][ny][current_direction] = visited[current_x][current_y][current_direction]
# 가다가 오른쪽
if not visited[nx][ny][(current_direction + 1) % 4]:
Q.append((nx, ny, (current_direction + 1) % 4))
visited[nx][ny][(current_direction + 1) % 4] = visited[current_x][current_y][current_direction] + 1
# 가다가 왼쪽
if not visited[nx][ny][(current_direction - 1) % 4]:
Q.append((nx, ny, (current_direction - 1) % 4))
visited[nx][ny][(current_direction - 1) % 4] = visited[current_x][current_y][current_direction] + 1
elif graph[nx][ny] == "#":
return visited[current_x][current_y][current_direction] - 1
print(bfs(sx, sy))
current_x, current_y, current_direction = Q.popleft()
dx, dy = move[current_direction]
nx, ny = current_x, current_y
while True:
nx = nx + dx
ny = ny + dy
이 부분이 중요한대 nx, ny 를 Currentx, currenty로 바꿔서 안 돌리게 되면 무한루프에 빠지게된다.
여기에서 좀 시간이 걸렸다.
댓글