(Python/파이썬) - 백준(BOJ) 3709번 : 레이저빔은 어디로

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

3709번: 레이저빔은 어디로

---

• 문제 : 

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

 

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

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

 

 

 

---

• 풀이 :

쉬운 구현 문제였습니다.

 

BFS나 DFS로 구현해도 정답을 도출할 수 있는 문제이며. 저는 direction 변수를 사용하여 구현하였습니다.

 

알고리즘의 흐름입니다.

 

1. 레이저의 초기 위치에 따라 방향 지정

 

2. 레이저가 다음으로 나아갈 좌표가 보드를 벗어났다면 그 때의 좌표를 출력하고 종료.

 

3. 레이저가 다음으로 나아갈 좌표가 거울의 좌표라면 방향회전. 이 때, 이미 방문했던 거울인지 표시하기 위해 (거울의 좌표, 방향)을 visited 집합에 저장

 

4. 만약 이번에 방문하는 좌표가 거울이면서 이전에 같은 방향으로 접근한 적이 있다면 보드 밖을 벗어날 수 없다는 것이므로 종료

 

 

추가 ) 문제를 풀다보니 깨닫게 된 것인데 보드를 벗어나지 못하는 경우는 사실상 존재할 수 없습니다.

 

4개의 거울이 직사각형의 각 꼭짓점에 위치힌다면 이론상 무한루프를 돌게 되는데 레이저의 좌표가 보드의 바깥에서 시작하므로 보드의 안쪽에서 어떠한 거울을 만나더라도 직진하여 그 다음 꼭짓점의 거울로 갈 수 없게 됩니다.

 

 

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline
dx = [-1,0,1,0]
dy = [0,1,0,-1]

for _ in range(int(input())):
    N, R = map(int,input().split())
    mirror = {tuple(map(int,input().split())) for _ in range(R)}
    visited = set()
    x,y = map(int,input().split())

    # 방향 설정 0 -> 3으로 상, 우, 하, 좌의 순서.
    if x == N+1:
        d = 0
    elif x == 0:
        d = 2
    elif y == N+1:
        d = 3
    else:
        d = 1

    # 다음 진행할는 방향을 검사
    while True:
        x += dx[d]
        y += dy[d]
        # 보드 밖으로 벗어났다면
        if not (0 < x <= N and 0 < y <= N):
            print(x,y)
            break
        # 이미 방문한 거울을 같은 방향에서 또다시 방문한다면 보드 밖을 벗어나지 못함
        if (x,y) in mirror and (x,y,d) in visited:
            print(0,0)
            break
        # 처음 거울을 방문했다면면
        elf (x,y) in mirror:
            visited.add((x, y, d))
            d = (d+1)%4