[백준] 3709 - 레이저빔은 어디로

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

3709번: 레이저빔은 어디로

그래프 연습문제를 찾다가 오늘은 적당한 난이도로 해보고자 solved.ac 기준 골드 5인 문제를 골랐다.

번역은 오역이 난무해서 문제 이해조차 제대로 안되고, 난이도는 또 너무 쉬워서 좋은 기억은 없었던 문제..

이 정도 난이도면 실버5~4 수준으로 넣어도 아무 상관 없을 것 같다..

---

번역에서 행과 열을 거꾸로 쓰는 바람에 매우 헷갈렸다.

행인데 어떻게 맨 밑에서 위로 쏘는건지...

이 문제는 원문으로 읽고, 그림을 그려 이해하는 것을 추천한다.

 

사실 매우 간단한 문제이다.

그냥 주어진 보드게임사이즈보다 2 큰 사이즈의 그리드를 그리고,

맨 아랫선을 X축, 맨 왼쪽선을 y축으로 놓은 다음

문제에서 주어진 입력값을 (x, y) 좌표값으로 생각하고,

문제의 출력은 최종 도착하는 좌표를 출력하면 된다.

 

아래에 그린 이미지를 봐주세요

문제의 예제입력1의 테스트 케이스 1을 그림으로 나타낸 것이다.

한국어 번역 기준, 우향우 거울을 만나면 그냥 진행방향의 오른쪽 90도로 꺾으면 된다.

v로 표시한 것이 시작점, 파란색 화살표가 진행경로, 파란 동그라미가 최종 도착지이다.

 

이 그림처럼, 주어진 격자 사이즈보다 2 큰 사이즈의 격자판을 그리고,

현재 진행방향을 체크하는 변수를 두어 그 방향에 맞게 시뮬레이션 하다가

(격자 사이즈가 최대 50*50이라 그냥 한칸식 시뮬레이션 해도 충분하다)

 

좌표가 0 또는 n+1인 곳에 도착하면 그대로 답을 출력하면 된다.

 

import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    n, r = map(int, input().split())
    graph = [[0 for _ in range(n+2)] for __ in range(n+2)]
    for i in range(r):
        x, y = map(int, input().split())
        graph[x][y] = 1
    start_x, start_y = map(int, input().split())

    if start_x == 0:
        direction = 0 # east
    elif start_x == n+1:
        direction = 2 # west
    elif start_y == 0:
        direction = 3 # north
    elif start_y == n+1:
        direction = 1 # south

    now_x = start_x
    now_y = start_y

    while True:
        if direction == 0:
            now_x += 1
        elif direction == 2:
            now_x -= 1
        elif direction == 3:
            now_y += 1
        elif direction == 1:
            now_y -= 1

        if graph[now_x][now_y] == 1:
            direction += 1
            direction %= 4

        if now_x == 0 or now_x == n+1 or now_y == 0 or now_y == n+1:
            print(now_x, now_y)
            break