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

문제 링크

6087번: 레이저 통신

문제 요약

c로 표시된 두 칸을 레이저로 연결시키고자 한다. 중간 중간에 거울을 놓아 레이저가 가는 방향을 90도 회전시킬 수 있을 때, 필요한 거울의 최소 갯수를 구해야 한다.

접근 방법

다익스트라 알고리즘으로 풀 수 있습니다. 방향을 90도 회전할 때는 가중치를 1, 현재 방향으로 직진할 때는 가중치를 0으로 두는 식으로, 거울을 표현할 수 있습니다.

이렇게 하면 중요한 점이, 어떤 칸에 재방문 했을 때, 방향이 다르면 이 둘은 별개로 봐야 한다는 것입니다. 같은 칸을 방문했더라도, 현재 보고 있는 방향이 다르면 방문할 수 있는 칸들이 달라집니다. 그에 따라서 거리를 체크하는 배열은 dist[4][101][101]과 같은 식으로, 3차원으로 선언해줄 필요가 있습니다.

나머지는 앞서 설명한대로, 방향을 바꿀 때 가중치를 1, 직진할 때 가중치는 0으로 하여 다익스트라 알고리즘을 구현해주면 됩니다.

처음에 이 문제를 읽자마자 든 생각은 0-1 BFS로 풀 수 있을거 같다는 생각이었습니다. 0-1 BFS는 덱을 이용해서, 가중치가 0인 경우에는 덱의 앞에, 1인 경우에는 덱의 뒤에 삽입을 하는 식으로 구현을 하는 BFS 방식입니다. 가중치가 0, 1 뿐인 그래프에서 사용이 가능합니다.

0-1 BFS와 다익스트라 모두 사용이 가능한 상황이라면면, 0-1 BFS가 더 우아한 방식이라는 (실제로 시간복잡도도 0-1 BFS가 낮습니다.) 글을 과거에 읽은 바가 있어서, 0-1 BFS로 구현을 했었지만 잘 풀리지가 않아서 다익스트라로 풀게 되었습니다. 풀고 나서 난이도 기여를 봤더니 0-1 BFS로 푸신 분들이 몇 분 계셔서 아쉬움이 남는 문제였습니다.

코드

#include <bits/stdc++.h>

using namespace std;

struct Data {
	int r, c, dist, dir;
};

struct Compare {
	bool operator()(const Data& a, const Data& b) {
		return a.dist > b.dist;
	}
};

const int MAX = 101, INF = 1e9;
int w, h, dist[4][MAX][MAX], dir[4][2] = { {0, 1}, {1, 0},  {0, -1}, {-1, 0} };
char b[MAX][MAX];

int rotate1(int dir) {
	dir++;
	return dir % 4;
}

int rotate2(int dir) {
	dir--;
	return (dir >= 0 ? dir : 3);
}

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

	cin >> w >> h;

	pair<int, int> s, e;
	bool flag = false;
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			cin >> b[i][j];

			if (b[i][j] == 'C') {
				if (!flag)
					flag = true, s = { i, j };
				else
					e = { i, j };
			}

			for (int k = 0; k < 4; k++)
				dist[k][i][j] = INF;
		}
	}

	priority_queue<Data, vector<Data>, Compare> pq;
	
	for (int i = 0; i < 4; i++) {
		pq.push({ s.first, s.second, 0, i });
		dist[i][s.first][s.second] = 0;
	}

	while (!pq.empty()) {
		auto now = pq.top();
		pq.pop();

		if (dist[now.dir][now.r][now.c] < now.dist)
			continue;

		if (now.r == e.first && now.c == e.second) {
			cout << now.dist;
			break;
		}

		int nr = now.r + dir[now.dir][0];
		int nc = now.c + dir[now.dir][1];

		if (nr >= 1 && nr <= h && nc >= 1 && nc <= w && b[nr][nc] != '*' && dist[now.dir][nr][nc] > now.dist) {
			dist[now.dir][nr][nc] = now.dist;
			pq.push({ nr, nc, now.dist, now.dir });
		}

		int ndir = rotate1(now.dir);
		
		if (dist[ndir][now.r][now.c] > now.dist + 1) {
			dist[ndir][now.r][now.c] = now.dist + 1;
			pq.push({ now.r, now.c, now.dist + 1, ndir });
		}

		ndir = rotate2(now.dir);

		if (dist[ndir][now.r][now.c] > now.dist + 1) {
			dist[ndir][now.r][now.c] = now.dist + 1;
			pq.push({ now.r, now.c, now.dist + 1, ndir });
		}
	}

	return 0;
}