[BOJ]6087번: 레이저 통신 (c++)

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

6087번: 레이저 통신

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

struct pos {
	int x, y;
};

int W, H;
const int MAX = 100;
char map[MAX][MAX + 1];
int mirror[MAX][MAX];
int dr_x[] = {0, 1, 0, -1};
int dr_y[] = {1, 0, -1, 0};

int bfs(pos start, pos end)
{
	// mirror배열을 -1로 초기화
	memset(mirror, -1, sizeof(mirror));

	// 큐에 시작위치 push
	queue<pos> q;
	q.push(start);

	while (!q.empty())
	{
		pos p = q.front();
		q.pop();

		// 끝점에 도착하면 : 끝점의 mirror값 반환
		if (p.x == end.x && p.y == end.y)
		{
			return mirror[p.x][p.y];
		}

		// 4방향 탐색
		for (int i = 0; i < 4; ++i)
		{
			int nx = p.x + dr_x[i];
			int ny = p.y + dr_y[i];

			/*
				한 방향으로 벽에 닿기 전 / map의 끝까지 mirror값을 매긴다.
				빛이 꺾이지 않는다면 mirror값은 직선방향으로 동일하기 때문.
			*/
			while (!(nx < 0 || nx >= H || ny < 0 || ny >= W))
			{
				if (map[nx][ny] == '*')
				{
					break;
				}

				/*
					mirror값이 아직 체크되지 않았다면
					현재의 거울 값 + 1 저장 후 큐에 push
				*/
				if (mirror[nx][ny] < 0)
				{	
					mirror[nx][ny] = mirror[p.x][p.y] + 1;
					q.push({nx, ny});
				}

				// 같은 방향 다음 위치로 이동
				nx += dr_x[i];
				ny += dr_y[i];
			}
		}
	}
	return -1;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	cin >> W >> H;
	vector<pos> SnE;
	for (int i = 0; i < H; ++i)
	{
		cin >> map[i];
		
		for (int j = 0; j < W; ++j)
		{
			// 시작점, 끝점
			if (map[i][j] == 'C')
			{
				SnE.push_back({i, j});
			}
		}
	}

	// 시작 ~ 끝 점까지 총 몇개의 거울이 필요한지 출력
	cout << bfs(SnE[0], SnE[1]);

	return 0;
}

 

 

지금까지는 현재 위치에 인접한 4지점만 탐색하는 bfs 문제를 풀었는데, 

이번에는 4방향으로 쭉~ 큐에 push하는 문제이다.

 

 

레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다. 

//   BEFORE                 //AFTER

7 . . . . . . .         7 . . . . . . .
6 . . . . . . C         6 . . . . . /-C
5 . . . . . . *         5 . . . . . | *
4 * * * * * . *         4 * * * * * | *
3 . . . . * . .         3 . . . . * | .
2 . . . . * . .         2 . . . . * | .
1 . C . . * . .         1 . C . . * | .
0 . . . . . . .         0 . \-------/ .
  0 1 2 3 4 5 6           0 1 2 3 4 5 6

위 그림에서 C끼리 연결되려면 거울이 총 3개가 필요하다.

레이저는 일직선으로 발사되기 때문에,

한 방향으로 쭉 이어지는 경로로는 거울개수가 그대로이다.

 

 

여기서 visit 체크 & 거울개수 체크하는 mirror배열을 어떻게 다루어야 할지 알수 있다. 

한 방향으로 쭉! 동일한 거울 개수를 매겨주는 것이다.

그리고 몽땅 큐에 push해준다.

// 4방향 탐색
for (int i = 0; i < 4; ++i)
{
	int nx = p.x + dr_x[i];
	int ny = p.y + dr_y[i];

	/*
		한 방향으로 벽에 닿기 전 / map의 끝까지 mirror값을 매긴다.
		빛이 꺾이지 않는다면 mirror값은 직선방향으로 동일하기 때문.
	*/
	while (!(nx < 0 || nx >= H || ny < 0 || ny >= W))
	{
		if (map[nx][ny] == '*')
		{
			break;
		}

		/*
			mirror값이 아직 체크되지 않았다면
			현재의 거울 값 + 1 저장 후 큐에 push
		*/
		if (mirror[nx][ny] < 0)
		{	
			mirror[nx][ny] = mirror[p.x][p.y] + 1;
			q.push({nx, ny});
		}

		// 같은 방향 다음 위치로 이동
		nx += dr_x[i];
		ny += dr_y[i];
	}
}

 

 

 

과정을 그림으로 간략하게 표현하자면 다음과 같다

1. 시작C로부터 직선 4방향은 거울개수가 0이다.

2. C의 오른쪽 칸부터 직선 4방향은 거울개수가 1이다. (이미 숫자 매겨진거 빼고)

3. C의 아래 칸부터 ~

4. C의 왼쪽 칸부터 ~ ~

5. C의 위쪽 칸부터 ~ 인데, 끝C를 만났다. 종료!

 

이렇게, mirror배열에 거울 개수를 매김과 동시에 큐에 push도 해준다.

그러다가 끝점을 만나면 끝점의 mirror값을 반환하며 bfs함수를 종료하면 된다.

// 끝점에 도착하면 : 끝점의 mirror값 반환
if (p.x == end.x && p.y == end.y)
{
	return mirror[p.x][p.y];
}

 

 

끝!