3709(레이저빔은 어디로) - 해결

레이저빔은 어디로

 

문제

레이저박스라는 게임은 정사각형  모양의 n x n 보드에서 진행한다. (체스판을 상상하면 된다) 레이저박스의 임의의 칸마다 우향우 거울이라는 장치가 설치되어 있고, 마지막으로 레이저 한개가 설치되어 있다. 레이저는 판의 끝에만 설치 될 수 있는데, 행의 맨 아래/맨 위, 열의 오른쪽 끝/왼쪽 끝에 설치 될 수 있다. 레이저에서 나온 빔은 그 행 혹은 열을 질러서 반대쪽을 비춘다.

게임은 우향우 거울을 임의의 칸마다 설치한 후, 레이저를 배치를 해 놓은 이후에 시작한다. 레이저를 켰을 때 나온 빔이 우향우 거울을 통과하면 진입한 방향과는 관계 없이 오른쪽으로 90도를 꺾어 다시 나아간다. 

레이저 빔이 마지막으로 어느 좌표를 향해 비춰지는지 구하라.

 

입력

첫 줄에는 테스트케이스의 총 개수가 주어진다.

테스트케이스의 첫 줄에는 보드의 크기 n(1 ≤ n ≤ 50)과 우향우 거울의 개수 r(1 ≤ r ≤ 50)이 주어진다.

이어지는 r개의 줄에는 우향우 거울이 배치된 좌표 x y가 주어진다.(좌표는 1부터 시작한다) 중복된 좌표는 있을 수 없고, 매 칸마다 최대 1개의 우향우 거울이 놓일 수 있다.

마지막 줄에는 레이저의 좌표가 주어진다. 레이저는 행과 열의 끝, 즉 판 밖에 위치해야 하므로 레이저의 좌표에는 0 혹은 n + 1이 포함된다. 

예를 들어, 2x2보드의 1행 맨 밑에서 위로 쏘아지는 레이저의 좌표는 (3, 1)로써 주어진다. 마찬가지로 6x6보드의 6열 왼쪽 끝에서 오른쪽 끝으로 쏘아지는 레이저의 좌표는 (6, 0)이 되겠다.

 

출력

매 테스트케이스마다 빔이 보드를 떠나는 좌표 X Y를 출력하라. 레이저의 좌표와 마찬가지로 빔은 보드 밖으로 떠나기에 좌표에는 0 혹은 n + 1이 포함된다. 

만약 빔이 보드 밖을 떠나지 않을 경우의 출력은 0 0이 된다.

---

일단 맵을 만들어서 거울을 설치하는 방법을 사용하였다.

그 후에 레이저를 설치하고 레이저의 위치에 따라 방향을 설정하였다.

그리고 반복을 통해서 방향으로 이동을 하고 거울의 존재와 끝의 도착을 확인하였다.

방향은 오른쪽으로만 이동하기 때문에 dirs을 오른쪽 방향으로 이동할 수 있도록 만들었다.

또한 마지막에 보드 밖을 떠나지 않는 경우는 없다. 그렇기 때문에 0 0이 출력되는 경우는 없다.

그 이유는 밖으로 못나가기 위해서는 사각형 모양으로 거울이 설치되어있어야 하는데 

그러면 그 사각형 안으로 레이저가 들어갈 방법이 없기 때문이다. 

 

import sys
input = sys.stdin.readline

T = int(input())

dirs = [(-1,0),(0,1),(1,0),(0,-1)]

# 테스트케이스
# 그리고 안되는 경우는 없다.
for tc in range(T):
    n, r = map(int,input().split())

    # 맵 만들기
    maps = []
    for _ in range(n+2):
        maps.append([0] * (n+2))

    # 거울 설치
    for _ in range(r):
        x, y = map(int,input().split())
        maps[x][y] = 1

    # 레이저 위치
    start =list(map(int,input().split()))
    # 레이저 위치에 따라 방향 설정
    if start[0] == 0:
        pre_dir = 2
    elif start[1] == n + 1:
        pre_dir = 3
    elif start[0] == n + 1:
        pre_dir = 0
    elif start[1] == 0:
        pre_dir = 1
    
    # 반복을 위해서
    nx, ny = start[0], start[1]
    # 찾아다니기
    while 1:
        # 방향 따라 이동
        nx, ny = nx + dirs[pre_dir][0], ny + dirs[pre_dir][1]
        # 다음 위치가 끝에 도착했다면
        # 출력하고 끝
        if nx == 0 or nx == n + 1 or ny == 0 or ny == n + 1:
            print(nx,ny)
            break
        # 1 이면 방향 전환
        # 방향은 무조건 오른쪽으로 바뀌기 때문에
        # 0 -> 1 -> 2 -> 3 -> 0 으로 바뀐다.
        elif maps[nx][ny] == 1:
            pre_dir = (pre_dir + 1) % 4