(c++)백준 6087번: 레이저 통신

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

6087번: 레이저 통신

[풀이]

※주의 할 것: 최소 거리를 구하는 게 아니라 거울 개수의 최솟값을 구하는 것!

- bfs 사용

- visited 2차원 배열에 각 좌표까지 가는 데 놓아야 하는 거울 개수의 최솟값을 저장한다.

 

#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct Mirror {
	int x, y;//설치된 거울 좌표
	int d;//방향
	int mirror;//거울 개수
};

int W, H;
char Map[100][100];
int visited[100][100];
const int dx[] = { -1,1,0,0 };//0:위, 1:아래, 2:왼쪽, 3:오른쪽
const int dy[] = { 0,0,-1,1 };
int startx, starty, destx, desty;

void bfs() {
	queue<Mirror>q;
	//모든 방향에 대해 큐에 넣어두기
	for(int i=0;i<4;i++){
		q.push({ startx,starty,i,0 });
	}
	visited[startx][starty] = 0;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int d = q.front().d;
		int m = q.front().mirror;
		q.pop();

		for (int i = 0; i < 4; i++) {
			//180도 회전은 무시
			if ((d == 0 && i == 1) || (i == 0 && d == 1) || (d == 2 && i == 3) || (i == 2 && d == 3))
				continue;
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nm = m;
			if (nx < 0 || nx >= H || ny < 0 || ny >= W)
				continue;
			if (Map[nx][ny] != '*') {
				//방향이 다를 때
				if (d != i)
					nm = nm + 1;
				//거울의 개수 + 1이 지금까지 구한 최소 거울의 수보다 작으면
				if (visited[nx][ny] >= nm) {
					visited[nx][ny] = nm;
					q.push({ nx,ny,i,nm });
				}
			}
		}
	}
}

void solution() {
	cin >> W >> H;
	string s;
	bool isFirstC = true;
	for (int i = 0; i < H; i++) {
		cin >> s;
		for (int j = 0; j < W; j++) {
			Map[i][j] = s[j];
			if (Map[i][j] == 'C' && isFirstC) {
				startx = i, starty = j;
				isFirstC = false;
			}
			else if (Map[i][j] == 'C' && !isFirstC) {
				destx = i, desty = j;
			}
			visited[i][j] = 9999999;
		}
	}
	bfs();
	cout << visited[destx][desty] << '\n';
}

int main() {
	solution();
	return 0;
}