[백준] 6087번 - 레이저 통신 / C++

문제

크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.

'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.

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

아래 그림은 H = 8, W = 7인 경우이고, 빈칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.

 

입력

첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)

둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.

• .: 빈 칸
• *: 벽
• C: 레이저로 연결해야 하는 칸

'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.

 

출력

첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

 

코드

#include <iostream>
#include <string>
#include <queue>
#include <cstring>

using namespace std;

struct pos
{
	int r;
	int c;
	int dir;
	int mirror;

	void init(int r, int c, int dir, int mirror)
	{
		this->r = r;
		this->c = c;
		this->dir = dir;
		this->mirror = mirror;
	}
};

int W;
int H;
int map[101][101];
pos src, dest;

int bfs()
{
	queue<pos> q;
	pos curr, next;
	int visit[101][101];		// src로부터 (r, c)에 도착하기 위해 필요한 거울 개수의 최솟값
	int d[] = {-1, 1, 0, 0};	// U-D-R-L
	int i;

	memset(visit, -1, sizeof(visit));
	// 출발지를 모든 방향에 대해 삽입
	curr = src;
	visit[curr.r][curr.c] = 0;
	for (i = 0; i < 4; i++)
	{
		curr.dir = i;
		q.push(curr);
	}
	while (!q.empty())
	{
		curr = q.front();
		q.pop();
		// 상하좌우에 대하여
		for (i = 0; i < 4; i++)
		{
			next.init(curr.r + d[i], curr.c + d[3 - i], i, curr.mirror);
			// 범위를 벗어나는 경우 패스
			if (next.r < 1 || next.r > H || next.c < 1 || next.c > W)
				continue;
			// 벽인 경우 패스
			if (map[next.r][next.c])
				continue;
			// 방향이 다른 경우 거울 설치
			if (curr.dir != next.dir)
				next.mirror++;
			// 처음 방문하거나 현재의 거울 개수가 최소인 경우 
			if (visit[next.r][next.c] == -1 || visit[next.r][next.c] >= next.mirror)
			{
				visit[next.r][next.c] = next.mirror;
				q.push(next);
			}
		}
	}
	// 목적지에 도착하기 위해 필요한 거울 개수의 최솟값을 리턴
	return visit[dest.r][dest.c];
}

int main()
{
	int i, j;
	string s;

	cin >> W >> H;
	for (i = 1; i <= H; i++)
	{
		cin >> s;
		for (j = 1; j <= W; j++)
		{
			if (s[j - 1] == '*')
				map[i][j] = 1;
			else if (s[j - 1] == 'C')
			{
				if (!src.r)
					src.init(i, j, 0, 0);
				else
					dest.init(i, j, 0, 0);
			}
		}
	}
	cout << bfs() << endl;
	return 0;
}

 

링크

6087번: 레이저 통신

inbdni/Baekjoon