백준 2151번 거울 설치

문제

채영이는 거울을 들여다보는 것을 참 좋아한다. 그래서 집 곳곳에 거울을 설치해두고 집 안을 돌아다닐 때마다 거울을 보곤 한다.

채영이는 새 해를 맞이하여 이사를 하게 되었는데, 거울을 좋아하는 그녀의 성격 때문에 새 집에도 거울을 매달만한 위치가 여러 곳 있다. 또한 채영이네 새 집에는 문이 두 개 있는데, 채영이는 거울을 잘 설치하여 장난을 치고 싶어졌다. 즉, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 거울을 설치하고 싶어졌다.

채영이네 집에 대한 정보가 주어졌을 때, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 하기 위해 설치해야 하는 거울의 최소 개수를 구하는 프로그램을 작성하시오.

거울을 설치할 때에는 45도 기울어진 대각선 방향으로 설치해야 한다. 또한 모든 거울은 양면 거울이기 때문에 양 쪽 모두에서 반사가 일어날 수 있다. 채영이는 거울을 매우 많이 가지고 있어서 거울이 부족한 경우는 없다고 하자.

거울을 어떻게 설치해도 한 쪽 문에서 다른 쪽 문을 볼 수 없는 경우는 주어지지 않는다.

입력

첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다.

출력

첫째 줄에 설치해야 할 거울의 최소 개수를 출력한다.

 

시작점에서 빛을 쏠 수 있는 출발 지점 전부 큐에 넣고 BFS 시작

거울 설치는 DFS 순열로 구하면 시간초과 이므로, 거울 설치 지점에서 그냥 .으로 취급하거나 거울로 취급하거나

케이스 나눠서 큐에 삽입

 

핵심은 visit 처리인데 거울이 있는 지점에서 이 지점을 방문한 케이스는 해당 지점을 방문 했는가 안했는가로만 판단하면 안됨. 거울에 반사되면서 해당 지점에 도착한 경우와 그냥 직진하면서 거친 경우 이후에 다른 케이스가 펼쳐지므로 구분지어야 함.

 

따라서 몇개의 거울을 설치한 후에 무슨 direction을 가지고 방문했는지 체크하려 했으나 런타임 발생. ㅅㅂ

따라서 해당 지점의 어떤 방향으로 접근시 현재 거친 거울수를 visit에 저장시키고

이후 같은 direction으로 해당 지점 방문시 저장된 거울수보다 적은 거울수를 거쳐서 온경우가 아니면 block 

의미가 없기때문.

 

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;

int N;
char arr[50][50];
int visit[50][50][4];
vector<pair<int, int> > vec;
int sy = -1;
int sx = -1;
int fy = -1;
int fx = -1;

int mina = 987654321;

struct Node {
	int y;
	int x;
	int dir;
	int num;
};

int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

//0 북 1 남 2 좌 3 우 


int main(void)
{

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> arr[i][j];

			if (arr[i][j] == '#' && sy == -1)
			{
				sy = i;
				sx = j;
			}
			if (arr[i][j] == '#' && sy != -1)
			{
				arr[i][j] = '.';
				fy = i;
				fx = j;
			}
		}
	}

	queue<Node> que;
	for (int i = 0; i < 4; i++)
	{
		int newy = sy + dy[i];
		int newx = sx + dx[i];
		if (newy >= 0 && newy < N && newx >= 0 && newx < N)
		{
			if (arr[newy][newx] != '*')
			{
				que.push({ sy,sx,i,0 });
			}
		}
	}

	while (!que.empty())
	{
		int y = que.front().y;
		int x = que.front().x;
		int dir = que.front().dir;
		int num = que.front().num;

		que.pop();
		if (y == fy && x == fx)
		{
			if (mina > num)
			{
				mina = num;
			}
		}
		for (int i = 0; i < 4; i++)
		{
			if (dir == i)
			{
				int newy = y + dy[i];
				int newx = x + dx[i];

				if (newy >= 0 && newy < N && newx >= 0 && newx < N)
				{
					if (arr[newy][newx] == '.')
					{
						if (!visit[newy][newx][dir] || visit[newy][newx][dir] > num)
						{
							visit[newy][newx][dir] = num;
							que.push({ newy,newx,dir, num });
						}
					}
					else if (arr[newy][newx] == '!')
					{
						if (!visit[newy][newx][dir] || visit[newy][newx][dir] > num)
						{
							visit[newy][newx][dir] = num;
							que.push({ newy,newx,dir, num });
						}

						if (dir == 0 || dir == 1)
						{
							if (!visit[newy][newx][2] || visit[newy][newx][2] > num + 1)
							{
								visit[newy][newx][2] = num + 1;
								que.push({ newy,newx , 2, num + 1 });
							}
							if (!visit[newy][newx][3] || visit[newy][newx][3] > num + 1)
							{
								visit[newy][newx][3] = num + 1;
								que.push({ newy,newx , 3, num + 1 });
							}
						}
						else if (dir == 2 || dir == 3)
						{
							if (!visit[newy][newx][0] || visit[newy][newx][0] > num + 1)
							{
								visit[newy][newx][0] = num + 1;
								que.push({ newy,newx , 0, num + 1 });
							}
							if (!visit[newy][newx][1] || visit[newy][newx][1] > num + 1)
							{
								visit[newy][newx][1] = num + 1;
								que.push({ newy,newx , 1, num + 1 });
							}
						}
					}
				}
			}
		}

	}

	cout << mina << endl;
}