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

 

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

 

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

6087번: 레이저 통신

---

 

 

해결전략

 

너비우선탐색 BFS

---

 

정답코드

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int dirY[4] = { -1, 0, 1, 0 };
int dirX[4] = { 0, -1, 0, 1 };
 
int w, h;						// w: 맵의 너비, h: 맵의 높이
int answer = 987654321;			// 최소 거울 개수, 초기값은 매우 큰 값으로 설정
vector<vector<char>> v;			// 맵 정보
vector<vector<vector<int>>> ch; // 각 위치에서의 거울 개수 및 방문 여부를 저장할 3차원 벡터
int startY, startX;             // 시작 위치
 
struct Info{
	int y, x, dir;
};
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	queue<Info> Q;
 
	cin >> w >> h;
	v.resize(h, vector<char>(w));
	ch.resize(h, vector<vector<int>>(w, vector<int>(4, -1)));
 
	bool bStart = false; // 시작 위치가 설정되었는지 여부
	for (int y = 0; y < h; y++){
		for (int x = 0; x < w; x++) {
			cin >> v[y][x];
			if (v[y][x] == 'C' && false == bStart) {
				// 시작 위치에서 4개 방향으로 탐색 시작
				Q.push({ y, x, 0 }); // 북
				Q.push({ y, x, 1 }); // 서
				Q.push({ y, x, 2 }); // 남
				Q.push({ y, x, 3 }); // 동
				// 시작 위치에서의 거울 개수를 0으로 설정
				ch[y][x][0] = 0;
				ch[y][x][1] = 0;
				ch[y][x][2] = 0;
				ch[y][x][3] = 0;
				startY = y;
				startX = x;
				bStart = true;
			}
		}
	}
 
	while(!Q.empty())
	{
		int y = Q.front().y;
		int x = Q.front().x;
		int dir = Q.front().dir;
		Q.pop();
 
		for(int i = 0; i < 4; i++){
			int ny = y + dirY[i];
			int nx = x + dirX[i];
			int ndir = i; // 다음 방향
 
			if (ny < 0 || h <= ny || nx < 0 || w <= nx || v[ny][nx] == '*') continue; // 범위 밖이거나 벽인 경우
			if (ny == startY && nx == startX) continue; // 시작 위치는 지나가지 않음
 
			if (v[ny][nx] == 'C'){ // 목표 위치('C') 도달 시
				if (dir != ndir) // 방향을 튼 경우, 거울 개수 증가
					answer = min(answer, ch[y][x][dir] + 1);
				else // 방향을 틀지 않은 경우
					answer = min(answer, ch[y][x][dir]);
				continue;
			}
 
			// 아직 방문하지 않은 경우 || 더 적은 거울을 사용해 도달할 수 있는 경우
			if (ch[ny][nx][ndir] == -1 || ch[ny][nx][ndir] > ch[y][x][dir] + (dir != ndir)) {
				Q.push({ ny, nx, ndir });
				ch[ny][nx][ndir] = ch[y][x][dir] + (dir != ndir); // 방향 전환 시 거울 개수 증가
			}
		}
	}
 
	cout << answer;
 
	return 0;
}

 

---