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

C에서 C까지 거울을 몇개 쓰면 레이저로 닿는지 찾는 문제입니다.

BFS로 문제를 해결했습니다.

queue<pair<pair<int, int>, pair<int, int> > > q 를 사용해서 정보를 저장했습니다. 
                    y좌표, x좌표, 최근방향, 거울사용횟수

C에서 상하좌우 방향으로 BFS를 진행하였고
같은 곳을 탐색하는 경우를 위해 visit를 통해 체크해주었습니다.
visit는 현재 거울사용 횟수도 저장하고 있으며,
이는 더 많은 거울을 사용해서 현재 위치를 탐색 것과  재방문을 방지 할 수 있습니다.
그리고 더 적은 거울을 사용한 경우에는 갱신되며, 이를통해 최적의 거울수를 체크할 수 있습니다.

주의해야할 점은
1. 시작점에서 상하좌우로 전부 큐에 넣어서 시작
2. visit배열을 통해 거울사용 수가 더 작은 경우에만 탐색가능
3. 도착지에 도달하더라도 BFS 종료를 하면 안됨

#include <iostream>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 987654321
using namespace std;

int main(int argc, char* argv[])
{
	int n, m;
	int move[4][2] = { { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 0 } };
	int visit[102][102];
	char map[102][102];
	vector<pair<int, int> > v;   // 시작좌표, 도착좌표
	queue <pair<pair<int, int>, pair<int, int> > > q;   // Y좌표, X좌표, 최근방향, 회전횟수

	cin >> m >> n;

	memset(map, '*', sizeof(map));

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> map[i][j];

			if (map[i][j] == 'C') {
				map[i][j] = '.';
				v.push_back(make_pair(i, j));
			}
			visit[i][j] = MAX;
		}
	}

	for (int i = 0; i < 4; ++i) {
		q.push(make_pair(make_pair(v[0].first, v[0].second), make_pair(i, 0)));
	}
	visit[v[0].first][v[0].second] = 0;

	while (!q.empty()) {
		int a = q.front().first.first;
		int b = q.front().first.second;
		int c = q.front().second.first;
		int d = q.front().second.second;
		q.pop();

		for (int i = 0; i < 4; ++i) {
			int y = a + move[i][0];
			int x = b + move[i][1];
			int z = d;

			if (i != c) {
				++z;
			}

			if (map[y][x] == '.' && visit[y][x] >= z) {
				visit[y][x] = z;
				q.push(make_pair(make_pair(y, x), make_pair(i, z)));
			}
		}
	}

	cout << visit[v[1].first][v[1].second] << endl;

	return 0;
}