[boj : 3709] 레이저빔은 어디로

www.acmicpc.net/problem/3709

3709번: 레이저빔은 어디로

문제 : nxn의 보드가 주어집니다. 레이저가 위치할 수 있는 곳은 0,n+1 구간입니다.

이때 레이저가 쏘면 들어오는 방향에 맞추어 오른쪽으로 꺽이는 거울이 있습니다. 보드의 범위를 벗어날때 그 좌표를 구하세요, 만약 벗어나지 못한다면 0 0 을 출력

 

해설 : 일단 레이저가 보드에서 벗어나지 못하는 경우는 존재하지 않습니다. 이유는 계속 무한루프가 돌려면 결국 그 무한루프에 들어가기 위한 거울이 존재해야하는데 이 거울이 존재하는 순간 무한루프는 깨저버리거든요.

어쨋든 들어오는 방향과 변경되는 방향을 미리 배열에 저장해 주고 거울을 만날때마다 변경하여 길을 쭉쭉 가게 해주면 됩니다.

필자는 0 : 상 1 : 우 2 : 하 3 : 좌 로 지정해 주었습니다.

 

dir        : 0 1 2 3

vardir    : 1 2 3 0

 

#include<bits/stdc++.h>

using namespace std;

int board[100][100];

void init();
void solve();
void go(int x, int y, int dir);

int main()
{
	int t;
	cin >> t;
	while (t--) {
		solve();
		init();
	}
}
void init()
{
	memset(v, 0, sizeof(v));
	memset(board, 0, sizeof(board));
}
void solve()
{
	int n, r, x, y;
	cin >> n >> r;
	for (int i = 0; i <= n + 1; i++) {
		board[0][i] = -1;
		board[i][0] = -1;
		board[n + 1][i] = -1;
		board[i][n + 1] = -1;
	}
	for (int i = 0; i < r; i++) {
		cin >> x >> y;
		board[x][y] = 1;
	}	
	cin >> x >> y;
	if (x == 0) go(x, y, 2);//하
	else if (x == n + 1)go(x, y, 0);//상
	else if (y == 0)go(x, y, 1);//우
	else go(x, y, 3);//좌
}
void go(int x, int y, int dir)
{
	int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };
	x += dx[dir];
	y += dy[dir];
	while (board[x][y] != -1) {
		if (board[x][y] == 1) 
			dir = (dir + 1) % 4;		
		x += dx[dir], y += dy[dir];
	}
	if (board[x][y] != -1)cout << 0 << " " << 0;
	else cout << x << " " << y;
	cout << "\n";
}