[Python] 3709번 레이저빔은 어디로

https://www.acmicpc.net/problem/3709

3709번: 레이저빔은 어디로

---

 

22/09/10

 

 

그룹 연습에서 풀었던 문제로, 시뮬레이션 문제를 오랜만에 풀어보는 터라 당황스러웠지만 재미있기도 했다.

---

 

문제 접근 방식:

 

 

특별한 알고리즘은 없고, 문제를 말 그대로 구현했다. 근데 보드를 딱 N*N크기로 구현한 것이 아니라, 그보다 위아래 왼쪽 오른쪽으로 1칸씩 크게 만들었다. 그 이유는 보드에서 레이저를 쏜다고 했으니, 그 레이저를 놓을 공간이 필요하다고 생각했기 때문이다.

 

우향우 거울은 진행방향에서 항상 오른쪽으로 꺾인다고 했으니, [북, 동, 남, 서] 방향의 리스트를 만들고, 거울을 만날 때마다 리스트의 인덱스를 +1 해준 뒤 4로 나누는 연산을 통해 방향이 꺾이는 것을 구현했다.

 

while문을 반복하여 돌면서 레이저 빛이 바깥으로 빠져나올 때까지 돌았다. 레이저 빛의 현재 위치를 now_pos라는 변수로 잡고 거울을 만날 때까지 직진, 이후 거울을 만나면 방향 전환을 반복하였다.

 

또한, 일정 숫자 이상 반복되어 만나면 무한루프에 빠지는 것으로 판단하였는데, 약간 이게 신뢰의 제출 느낌이라 내가 푼 풀이를 완전히 정당화하지는 않았다. 하지만, 숫자를 크게 잡았기 때문에 적어도 그 케이스 안에서는 충분히 테스트 케이스들을 통과할 것이라고 생각했다.

 

보드의 크기가 최대 50까지이고, 만약 무한루프에 빠지지 않는다면 적어도 같은 칸을 5번 이상 지나지는 않을 것이라고 생각하여(왜냐하면 우향우 거울이 있는 칸이라면, 서로 다른 4방향이 들어온다면 나가는 방향이 전부 다 다르기 때문) 50*50*5 = 1250보다 훨씬 큰 숫자인 50000을 기준으로 삼았다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 3709번 레이저빔은 어디로
import sys
input = sys.stdin.readline

test_case = int(input())
for _ in range(test_case):
    N, R = map(int, input().rstrip().split())
    board = [[0 for _ in range(N+2)] for _ in range(N+2)]
    for _ in range(R):
        x, y = map(int, input().rstrip().split())
        board[x][y] = 1
    beam_pos = tuple(map(int, input().rstrip().split()))
    dir_li = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    now_dir = 0
    stop = 0
    flag = True
    if beam_pos[0] == 0:
        now_dir = 1
    elif beam_pos[0] == N+1:
        now_dir = 3
    elif beam_pos[1] == 0:
        now_dir = 0
    else:
        now_dir = 2
    now_pos = (beam_pos[0] + dir_li[now_dir][0], beam_pos[1] + dir_li[now_dir][1])
    while True:
        if stop > 50000:
            flag = False
            break
        if now_pos[0] == 0 or now_pos[0] == N+1 or now_pos[1] == 0 or now_pos[1] == N+1:
            break
        if board[now_pos[0]][now_pos[1]] == 1:
            now_dir = (now_dir + 1) % 4
        now_pos = (now_pos[0] + dir_li[now_dir][0], now_pos[1] + dir_li[now_dir][1])
        stop += 1
    if flag:
        print(*now_pos)
    else:
        print(0, 0)