BOJ(C++) / 백준 6087 : 레이저 통신

백준 6087 : 레이저 통신

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

6087번: 레이저 통신

7 . . . . . . .         7 . . . . . . .
6 . . . . . . C         6 . . . . . /-C
5 . . . . . . *         5 . . . . . | *
4 * * * * * . *         4 * * * * * | *
3 . . . . * . .         3 . . . . * | .
2 . . . . * . .         2 . . . . * | .
1 . C . . * . .         1 . C . . * | .
0 . . . . . . .         0 . \-------/ .
  0 1 2 3 4 5 6           0 1 2 3 4 5 6

 

코드

//백준 6087 레이저 통신
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;


#define INF 100001

int W, H;
vector<string> board;
vector<pair<int, int>> cLocation;
int nexti[4] = { 0,0,1,-1 }, nextj[4] = { 1,-1,0,0 }; // 동,서,북,남
int mirror[101][101] = { 0, };

struct location {
	int i;
	int j;
	int preDirection; //이전 방향
	int mirrorNum;
};

void BFS(int i, int j) {
	queue<location> q;
	q.push({ i,j,-1,0 });
	mirror[i][j] = 0;

	while (!q.empty()) {
		int ci = q.front().i;
		int cj = q.front().j;
		int cDirection = q.front().preDirection;
		int cNum = q.front().mirrorNum;
		q.pop();

		for (int k = 0; k < 4; k++) {
			int ni = ci + nexti[k];
			int nj = cj + nextj[k];

			if (ni < 0 || nj < 0 || ni >= H || nj >= W) {
				continue;
			}
			if (board[ni][nj] == '*') {
				continue;
			}

			//처음 방향 없음
			if (cDirection == -1) {
				mirror[ni][nj] = mirror[ci][cj];
				q.push({ ni,nj, k, mirror[ni][nj]});
			}
			// 같은 방향
			else if (cDirection == k) {
				if ( mirror[ni][nj] >= cNum) {
					mirror[ni][nj] = cNum;
					q.push({ ni,nj, k, mirror[ni][nj]});
				}
			}
			// 다른 방향
			else if (cDirection != k) {
				if (mirror[ni][nj] >= cNum + 1) {
					mirror[ni][nj] = cNum + 1;
					q.push({ ni,nj, k, mirror[ni][nj]});
				}
			}
		}
	}
}

int main() { 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> W >> H;

	for (int i = 0; i < H; i++) {
		string s = "";
		for (int j = 0; j < W; j++) {
			char c;
			cin >> c;
			s += c;
			if (c == 'C') {
				cLocation.push_back({ i,j });
			}
			mirror[i][j] = INF;
		}
		board.push_back(s);
	}

	BFS(cLocation[0].first, cLocation[0].second);
	cout << mirror[cLocation[1].first][cLocation[1].second] << "\n";

	return 0;
}

설명

 

이번 문제는 BFS문제이지만 생각해봐야 할 것들이 많은 문제다.

 

레이저는 방향이 달라질 때 설치되어야한다. 따라서 queue에 위치와 방향, 거울 개수를 저장해준다.

예를 들어서 이전 방향이 '←' 였다면 다음 진행할 방향이 '←'라면 거울을 설치할 필요가 없지만 '↓', '↑', '→'이라면 거울을 설치해서 방향이 바꿔야 한다. 

 

최단거리라 해서 설치해야 하는 거울 개수가 최솟값은 아니다.

다음 지도를 봤을 때 오른쪽 지도는 최단거리는 9이지만 설치해야 하는 거울의 개수는 5개이다. 오히려 최단거리가 아닌 왼쪽 루트로 갔을때 설치해야 하는 거울이 3개로 더 적다.

 

다음과 같은 조건들을 잘 생각해서 문제를 구현할 수 있다. 

• 처음 시작일 때는 모든 방향으로 거울 설치하지 않고 움직일 수 있다.
• 같은 방향일 때는 거울 추가 없이 값이 원래 위치의 값보다 작거나 같을 때 queue에 push 한다.
• 다른 방향일 때는 설치해야 할 거울을 추가한 값이 원래 위치의 값보다 작거나 같을 때 queue에 push한다.

(각 칸은 여러방향에서 여러번 올 수있다는 사실을 알아두어야 한다. 어느 방향에서 오느냐가 다음 값에 영향을 미친다.)

 

고찰

걸린시간 : 두시간

처음 구현할때는 모든 대각선 위치에 있는 지점들을 +1해주는 방식으로 문제를 구현했지만, 완전히 잘못된 접근법이었다. 구현하기 전에 시뮬레이션을 해본 후 구현을 한다면 시간이 더 단축될 거 같다. 결국 구글링으로 문제를 해결하였지만 다음번에는 구글링 없이 문제를 구현하는 능력을 길러야겠다.

 

난이도

Gold 4