boj, 백준) 2151. 거울 설치 ( C / C++)

1. 문제 링크

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

2151번: 거울 설치

2. 문제 개요

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

 

3. 문제 힌트

※구현

   - BFS

   - 반사되는2가지, 거울을 놓지 않았다 생각하고 지나가기.

   - 먼저 도착하는것이 정답이 아니다.

   

문제에서 거리는 최대 50이지만 이해를 위해 길게 설정함

위와 같은 경우는 위로 도착하는 것이 더 빨리 도착한다. 거리가 짧기 때문이다. 하지만 반사되는 거울의 수는 더 많다. 원하는 답이 아니다.

이에 반해서 오른쪽으로 둘러오는 빛은 거울을 2번반사한다. 하지만 거리가 멀기 때문에 BFS상 늦게 도착하게 된다. 따라서 Queue에 아무것도 없을 때까지 탐색해야 한다.

 

 

※시간 단축

 - 어떠한 거울에 3번 반사되어 온 빛이 이미 반사되어 지나간 상태다. 10번 반사되어 온 빛이 도착하면 어차피 동일한 경로를 쫓아갈 테고 어차피 답이 되지 않는다. 

 

 

4. 문제 풀이

 우선 맵을 char배열에 입력받았다.

그리고 시작점 아무거나 하나 잡아서 BFS를 4방향으로 시작해준다.

 

시간 단축을 위해서 Queue에서 pop 하자마자 비교해준다. 더 진행해도 의미 있는 빛인지 아닌지 판별.

'*'이거나 경계를 벗어나면 continue,

거울을 놓을 수 있는 위치에 도달하면 거울을 놓지 않는 경우, 반사되는 경우 2가지, 총 합쳐서 3가지를 Queue에 넣어준다. 반사되는 빛은 반사 횟수(거울 개수)를 1 증가시킨 채 Queue에 넣는다.

'.'을 만나면 아무것도 하지 말고 그냥 그 방향 그래도 전진한다.

모든 빛이 출구를 통해 빠져나올 때, 가장 적게 반사된 빛을 찾아서 출력한다.

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n, mirr_num = 0, ans=987654321;
char map[50][50];
int visited[50][50][4];

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

struct COORD
{
	int y, x;
	int time;
	int dir;
};

pair<int,int> reflect_dir(int cur_dir)
{
	if (cur_dir <=1)//from east, west
		return make_pair(2, 3);		
	else //from north, south
		return make_pair(0, 1);
}

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

	for (int i = 0; i < n; ++i)
		scanf("%s", map[i]);

	COORD s;

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
		{
			if (map[i][j] == '#')
			{
				s.y = i; s.x = j;
			}
			
			for (int dir = 0; dir < 4; dir++)
				visited[i][j][dir] = 987654321;
		}
	
	queue<COORD> q;
	s.time = 0;
	for (int i = 0; i < 4; ++i)
	{
		s.dir = i;
		q.push(s);
	}

	map[s.y][s.x] = '*';	//to prevent returning to starting place

	while (!q.empty())
	{
		COORD cur = q.front(); q.pop();

		if (visited[cur.y][cur.x][cur.dir] <= cur.time)
			continue;
		visited[cur.y][cur.x][cur.dir] = cur.time;
		
		//advance
		COORD next;
		next.y = cur.y + dy[cur.dir];
		next.x = cur.x + dx[cur.dir];
		next.time = cur.time;

		//'*' or out of boundary
		if (map[next.y][next.x] == '*' || next.x < 0 || next.y < 0 || next.x >= n || next.y >= n)
			continue;

		if (map[next.y][next.x] == '!')	//'!'
		{
			//if idont put mirror here
			next.dir = cur.dir;
			q.push(next);

			//if i put mirror here.
			next.time++;
			pair<int, int> new_dir = reflect_dir(cur.dir);

			next.dir = new_dir.first;	
			q.push(next);
			next.dir = new_dir.second;
			q.push(next);
			
		}
		else if (map[next.y][next.x] == '.') //'.'
		{
			next.dir = cur.dir;
			q.push(next);
		}
		else if (map[next.y][next.x] == '#')	//goal
		{
			ans = min(ans, (int)next.time);
		}
	}
	
	printf("%d", ans);

	return 0;
}

6. 결과 사진

지적, 댓글 언제나 환영입니다~