6087 레이저통신

알고리즘(BFS)

1. visit 배열을 int로 선언. 이제까지 온 것들의 거울 개수를 저장
2. 갈 수 잇고, visit에 저장된 거울 개수와 같거나 작으면 이동 시킴

주의점

같은 레이저에 도달하지 않기위해 설정한 row != start.row && col != start.col 은 작동하지 않음
-> 같은 줄에만 있어도 애들이 안가기 때문
-> 따라서 다음처럼 조건문을 짜야함.
	row != start.row || col != start.col

코드

#include <iostream>
#include <list>
 
using namespace std;
 
typedef struct Location {
	int row;
	int col;
	int direction;		// 0 : 초기, 1 : 위 2 오 3 아 4 왼
	int mirror;
} Location;
 
int R, C;
Location start;
char map[100][100];
int visit[100][100];
int BFS();
 
int main() {
	cin >> C >> R;
	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'C') {
				start.row = i;
				start.col = j;
			}
			visit[i][j] = 2000000000;
		}
	cout << BFS();
}
int BFS() {
	list<Location> q;
	q.push_back({ start.row, start.col, 0, 0 });
	visit[start.row][start.col] = 0;
	int minMirror = 2000000000;
 
	while (!q.empty()) {
		int row = q.front().row, col = q.front().col, d = q.front().direction, m = q.front().mirror;
		q.pop_front();
 
 
		if ( map[row][col] == 'C') {
			minMirror = m;
		}
		if (row > 0 && map[row - 1][col] != '*' && d != 3) {
			int nextMirror = d != 4 ? d != 2 ? m : m + 1 : m + 1;
			if (nextMirror <= visit[row - 1][col]) {
				q.push_back({ row - 1, col, 1, nextMirror });
				visit[row - 1][col] = nextMirror;
			}
		}
		if (row < R - 1 && map[row + 1][col] != '*' && d != 1) {
			int nextMirror = d != 4 ? d != 2 ? m : m + 1 : m + 1;
			if (nextMirror <= visit[row + 1][col]) {
				q.push_back({ row + 1, col, 3, nextMirror });
				visit[row + 1][col] = nextMirror;
			}
		}
		if (col > 0 && map[row][col - 1] != '*' && d != 2) {
			int nextMirror = d != 3 ? d != 1 ? m : m + 1 : m + 1;
			if (nextMirror <= visit[row][col - 1]) {
				q.push_back({ row, col - 1, 4, nextMirror });
				visit[row][col - 1] = nextMirror;
			}
		}
		if (col < C - 1 && map[row][col + 1] != '*'&& d != 4) {
			int nextMirror = d != 3 ? d != 1 ? m : m + 1 : m + 1;
			if (nextMirror <= visit[row][col + 1]) {
				q.push_back({ row, col + 1, 2, nextMirror });
				visit[row][col + 1] = nextMirror;
			}
		}
	}
	return minMirror;
}