[백준/c++] 6087 레이저 통신

문제

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

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

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

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

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

입력

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

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

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

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

출력

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

구현해야할 조건

시작점을 하나 지정하고 도착점을 지정하게된다. 어쨌든 C가 2개 나오기로 결정되어있으니까!
그렇게 시작된다면 C에서 4방향으로 나갈 것을 정해주고 방향이 바뀐다면? 거울이 있다는 뜻이다. 그렇다고 한번 할때마다 거울을 확인 할 수 없으니까 BFS를 활용해서 방향이 바뀐다면? 거울이 있는것! 그렇게 이동을 하면서 거울의 개수도 카운트해주고 도착지점까지 거울 몇개와 몇번의 이동이 있는 지 확인 가능한 struct를 만들어 보자!

code

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

#define MAX 101
#define INF 987654321
using namespace std;

typedef struct{
	int y;
	int x;
	int dir;
	int cnt;
}laser;

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

int h,w;
int dist[MAX][MAX];
char board[MAX][MAX];

vector<pair<int,int> > v;
queue<pair<int,int> > q;

int main()
{
	
	cin >> w >> h;
	
	for(int i = 0; i < h; i++)
	{
		for(int j = 0; j < w; j++)
		{
			cin >> board[i][j];
			dist[i][j] = INF;
			if(board[i][j] == 'C')
				v.push_back({i,j});
		}
	}
	
	q.push(v[0]);
	dist[v[0].first][v[0].second] = 1;
	queue<laser> lasers;
	
	
	for(int i = 0; i < 4; i++)
	{
		int y = q.front().first;
		int x = q.front().second;
		int dir = i;
				
		lasers.push({y,x,dir,0});
	}
	
	q.pop();
	
	while(!lasers.empty())
	{
		int y = lasers.front().y;
		int x = lasers.front().x;
		int dir = lasers.front().dir;
		int cnt = lasers.front().cnt;
		lasers.pop();
		
		
		for(int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nCnt = cnt;
			
			if(nx < 0 || ny < 0 || nx >= w || ny >= h) // 범위를 넘어서거나
				continue;
			if(board[ny][nx] == '*') // 벽에 있다
				continue;
			if(dir != i) // 방향이 바뀌면 바뀐 횟수 카운트!
				nCnt = nCnt + 1;
				
			if(dist[ny][nx] >= nCnt)
			{
				dist[ny][nx] = nCnt; // 이동횟수가 더 적으면 dist에 넣어주기
				lasers.push({ny,nx,i,nCnt});
			}
		}
	}
	
	cout << dist[v[1].first][v[1].second];
	
	return 0;
}