[백준 6087] 레이저 통신

분류 : bfs

 

요구사항

최소로 거울을 설치하여 시작점에서 도착점으로 이동할 수 있는 거울의 개수

 

풀이

일반적인 bfs는 visit배열에 방문 여부를 저장하는데 이 문제는 visit배열에 방향을 바꾼 횟수를 저장한다

문제에서 거울을 만나면 방향을 바꾼다고 햇으니 모든 map에 대해 최소의 visit배열을 구하면 답을 구할 수 있다

C두개중 하나는 시작점 나머지는 도착점으로 설정한다

시작할때는 모든 방향에 대해서 방향을 변경한거로 조건을 주어야한다

//0일때는 무조건 1 증가
if (cnt == 0) {
NminC = minC + 1;
}

 

#include<iostream>
#include <queue>

using namespace std;

int n, m;
char map[110][110];
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };
int visit[110][110];
int starti;
int startj;
int endi;
int endj;
struct go {
	int x;
	int y;
	int dir;
	int minchange;
};
void solve() {


	int d = 0;
	queue<go> q;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			visit[i][j] = 9821;
		}
	}
	q.push({ starti,startj,0,0 });
	visit[starti][startj] = 1;
	int cnt = 0;
	while (!q.empty()) {
		int r = q.front().x;
		int c = q.front().y;
		int nowdir = q.front().dir;
		int minC = q.front().minchange;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			int NminC = minC;
			if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
			if (map[nr][nc] == '*') continue;

			//방향바꼇으면
			if (cnt != 0) {
				if (nowdir != i) {
					NminC = minC + 1;
				}
			}
			//0일때는 무조건 1 증가
			if (cnt == 0) {
				NminC = minC + 1;
			}

			if (map[nr][nc] == '.' || map[nr][nc] == 'C') {
				//방문했더라고 최소로 이동하면 업데이트
				if (visit[nr][nc] >= NminC) {
					visit[nr][nc] = NminC;
					q.push({ nr,nc ,i,NminC });
				}
			}
		}
		cnt++;
	}

}

int main() {
	cin >> n >> m;
	int cnt = 0;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (cnt == 0 && map[i][j] == 'C') {
				starti = i;
				startj = j;
				cnt++;
			}
			if (cnt == 1 && map[i][j] == 'C') {
				endj = j;
				endi = i;
			}

		}
	}
	solve();
	/*
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (visit[i][j] == 9821)
				cout << "0" << " ";
			else cout << visit[i][j] << " ";
		}
		cout << endl;
	}
	*/
	cout << visit[endi][endj] - 1 << endl;
}