[백준] 6087-레이저 통신(C++)

문제링크: https://www.acmicpc.net/problem/6087

6087번: 레이저 통신

bfs문제입니다.

 

접근방식

 

1. 결국 몇번 꺾여서 목표에 도달할 수 있는지 묻는 문제

2. bfs를 통해서 구현하기로 결정. 일반적인 형태라는 다르게 큐를 구현해야함

 

문제풀이 

 

1. 큐에는 현재 좌표, 거울의 개수, 도달한 방향순으로 저장

2. 만약 거울의 갯수가 같거나 작다면 큐에 넣어주면서 거울 갯수를 탐색

이때, visited함수에 최소 거울의 갯수를 저장

 

 

 

 

정답 코드

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

int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };
char arr[100][100];

vector <pair<int, int>> laser;
int visited[100][100] = { 0, };
int w, h;

int val, temp;

void bfs() {

	queue <pair<pair<int, int>, pair<int, int>>> que; //좌표, 거울 갯수, 방향순으로 넣을거
	que.push(make_pair(make_pair(laser[0].first, laser[0].second), make_pair(0, -1)));

	while (!que.empty()) {
		int y = que.front().first.first;
		int x = que.front().first.second;
		int mirror = que.front().second.first;
		int dir = que.front().second.second;
		que.pop();
		int temp;
		for (int i = 0; i < 4; i++) {
			int ny = y + y_ar[i];
			int nx = x + x_ar[i];
			if (ny < 0 || ny >= h || nx < 0 || nx >= w || arr[ny][nx] == '*' )
				continue;
			temp = mirror;
			if (dir != i)
				temp++;
			if (visited[ny][nx] >= temp) {
				visited[ny][nx] = temp;
				que.push(make_pair(make_pair(ny, nx), make_pair(temp, i)));
			}



		}

		
	}



}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	
	cin >> w >> h;
	for (int i = 0; i < h; i++) {
		cin >> arr[i];
		for (int j = 0; j < w; j++) {
			if (arr[i][j] == 'C')
				arr[i][j] = '.', laser.push_back(make_pair(i, j));
			visited[i][j] = 1000000000;
			
		}
	}

	bfs();
	/*
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cout << visited[i][j] << ' ';
		}
		cout << endl;
	}
	*/

	cout << visited[laser[1].first][laser[1].second] - 1 << endl;

	return 0;
}