레이저 통신 (feat. 백준, 6087번)

레이저 통신
https://www.acmicpc.net/problem/6087

6087번: 레이저 통신

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int W, H, dx[4], dy[4], dist[101][101];
char arr[101][101];
vector<pair<int, int>> lasers;
void bfs(register int x, register int y) {
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	dist[x][y] = -1;
	while (!q.empty()) {
		auto p = q.front(); q.pop();
		x = p.first, y = p.second;
		for (register int d = 0, nx, ny; d < 4; ++d) {
			nx = x + dx[d], ny = y + dy[d];
			while (true) {
				if (nx < 1 || nx > H || ny < 1 || ny > W)	// 범위 벗어났으면 종료
					break;
				if (arr[nx][ny] == '*')		// 벽이면 종료
					break;
				if (dist[nx][ny] < dist[x][y] + 1)	// 이전에 들렀었고 현재가 더 거리가 크면 종료
					break;
				dist[nx][ny] = dist[x][y] + 1;
				if (arr[nx][ny] == 'C')		// 다른 레이저 위치면 종료
					return;
				q.push(make_pair(nx, ny));
				nx += dx[d], ny += dy[d];
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	cin >> W >> H;
	for (register int h = 1, w; h <= H; ++h)
		for (w = 1; w <= W; ++w) {
			cin >> arr[h][w], dist[h][w] = static_cast<int>(1e8);
			if (arr[h][w] == 'C')
				lasers.push_back(make_pair(h, w));
		}
	bfs(lasers[0].first, lasers[0].second);
	cout << dist[lasers[1].first][lasers[1].second];
	return 0;
}
// *&)*@*

1. 하나의 레이저로부터 같은 방향으로는 같은 값을 설정한다는 개념으로 풀이했습니다.
2. 즉, 레이저 위치로부터 왼쪽 방향으로 벽이 올때까지 모든 거리는 1 이다. 와 같은 개념입니다.
3. 그리고 이후 동일한 위치에 도착했을때 이전의 거리보다 더 큰 경우는 거울을 더 많이 설치해야 한다는 조건이므로 bfs를 진행하지 않았습니다.