JinWoo Kim

백문이 불여일견, 백견이 불여일행.

2 minute read

1. 거울

  • 세로 N, 가로 M 크기의 상자가 있다. 이 상자 안에는 몇 개의 거울이 들어 있다. 상자를 위에서 봤을 때, 거울은 한 칸 안에 대각선 모양으로 들어있다고 한다.

  • 또, 상자의 테두리를 따라서 칸마다 구멍이 뚫려 있다. 편의상 구멍은 왼쪽 위에 뚫려있는 것부터 시계 반대 방향으로 1, 2, …, 2N+2M 의 번호가 붙어 있다. 예를 들어 다음과 같은 경우를 보자.

    이미지

  • 이제 이 상자에 뚫려있는 구멍으로 빛을 쏜다고 생각해보자. 1번 구멍으로 쏠 경우에는 (1, 2)의 위치에 있는 거울에 반사되어 9번 구멍으로 빛이 가게 된다. 또, 2번 구멍으로 빛을 쏠 경우에는 (2, 2)의 위치에 있는 거울과 (1, 2)에 있는 거울에 차례로 반사되어 7번 구멍으로 빛이 나가게 된다.

  • 이와 같이 상자의 모양이 주어졌을 때, 각 구멍으로 쏜 빛이 나가게 되는 구멍을 구하는 프로그램을 작성하시오.

입력

  • 첫째 줄에 N, M (1 ≤ N, M ≤ 1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 상자의 모양이 주어진다.
  • 거울이 있는 위치는 1로, 거울이 없는 위치는 0으로 주어진다.
  • 거울은 / 모양으로만 놓일 수 있다고 하자.

출력

  • 첫째 줄부터 차례로 1번 구멍으로 쏜 빛이 나가는 구멍의 번호, 2번 구멍으로 쏜 빛이 나가는 구멍의 번호, …, 2N+2M번 구멍으로 쏜 빛이 나가는 구멍의 번호를 출력한다.

풀이

import sys

N, M = list(map(int, sys.stdin.readline().split()))

box = [[] for x in range(0, N)]
nums = [x for x in range(1, 2 * N + 2 * M + 1)]

for i in range(0, N):
    box[i] = list(map(int, sys.stdin.readline().split()))

# 1~ 2N+2M = 번호 일때,
# 1~N : 왼쪽변
# N+1~N+M : 밑변
# N+M+1~2N+M : 오른쪽 변
# 2N+M+1 ~ 2N+2M

# 각 번호에서의 시작점 좌표 역시 구한다.

# left = nums[0:N]
# bottom = nums[N:N + M]
# right = nums[N + M:2 * N + M]
# top = nums[2 * N + M:]

# 각 번호에서 쏘아진 빛의 초기 방향을 정의
# 왼쪽 => 1,0로 나아감
# 아래쪽 => 0,-1으로 나아감
# 오른쪽 => -1,0로 나아감
# 위쪽 => 0,1로 나아감

ray_initial = [[1, 0]] * N + [[0, -1]] * M + [[-1, 0]] * N + [[0, 1]] * M

# 빛의 시작점 좌표
# left : (0,0~N)
# bottom : (0~M,N)
# right: (M,(N~0, -1))
# top : ((M~0,-1),0)

start_points = [[0, x] for x in range(0, N)] + [[x, N - 1] for x in range(0, M)] + \
               [[M - 1, x - 1] for x in range(N, 0, -1)] + [[x - 1, 0] for x in range(M, 0, -1)]

for i in range(0, 2 * N + 2 * M):
    x, y = start_points[i]
    ray = ray_initial[i]
    now = [x, y]
    while 0 <= y < N and 0 <= x < M:
        now = [x, y]
        x_ray, y_ray = ray
        if box[y][x] == 1:
            ray = [-y_ray, -x_ray]
            x_ray, y_ray = ray
        x += x_ray
        y += y_ray

    end_point = [x for x in range(0,len(start_points)) if start_points[x] == now and ray_initial[x] == [-x_ray,-y_ray]]
    print(end_point[0] + 1, end=' ')

채점 결과

  • 정답

리뷰

  • 각 번호에서 시작하는 빛의 방향을 ray_initial로 정의해준다.

  • 각 번호에서 빛이 뻗어나가는 시작점을 start_points로 정의해준다.

  • 각 번호에 대해 출발점에서 ray를 발사하고, 거울을 만나지 않는다면 ray만큼 인덱스를 더한다.

    • 거울을 만난다면, 방향을 반전시킨다.

  • 인덱스중 어느 하나가 box 범위를 벗어날때까지 위의 반복문을 진행한다.

  • 반복문 종료시(빛이 box를 벗어날때) 빛의 방향과 마지막 빛의 위치를 통해 빛이 나가는 구멍을 출력한다.

You May Also Enjoy