백준 3709 레이저빔은 어디로

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

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이 된다.

예제 입력 1 

2

2 3

1 1

1 2

2 2

3 1

3 6

1 1

1 3

2 2

2 3

3 1

3 2

2 0

예제 출력 1 

2 0 0 2

---

[풀이 과정]

1. 

 

---

[소스 코드]

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int MAX = 55;

int n, r, T, arr[MAX][MAX], final_x, final_y;
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
struct info {
	int x, y, d;
};
bool visited[MAX][MAX];

bool move(int a, int b, int dir) {
	queue <info> q;
	q.push({ a, b, dir });

	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int d = q.front().d;
		q.pop();


		int nx = x + dx[d];
		int ny = y + dy[d];

		if (nx < 1 || nx > n || ny < 1 || ny > n) {
			final_x = nx;
			final_y = ny;
			return true;
		}

		if (!visited[nx][ny] && arr[nx][ny] == 1) {
			d = (d + 1) % 4;
			q.push({ nx, ny, d });
		}
		else if (visited[nx][ny] && arr[nx][ny] == 1) return false;

		else if (arr[nx][ny] == 0) q.push({ nx, ny, d });
	}
}

int main() {
	scanf("%d", &T);

	for (int t = 0; t < T; t++) {
		scanf("%d %d", &n, &r);

		memset(visited, 0, sizeof(visited));
		memset(arr, 0, sizeof(arr));
		for (int i = 0; i < r; i++) {
			int mx, my;
			scanf("%d %d", &mx, &my);

			arr[mx][my] = 1;
		}

		int rx, ry, rd;
		scanf("%d %d", &rx, &ry);

		if (rx == 0) rd = 2;
		else if (rx == n + 1) rd = 0;
		else if (ry == 0) rd = 1;
		else rd = 3;

		if (move(rx, ry, rd)) printf("%d %d\n", final_x, final_y);
		else printf("0 0\n");
	}
	return 0;
}