방과후
ALGORITHM NOTE약 2분

BOJ 6087 - 레이저 통신

거울로 전 세계와 통신하자!

#algorithm#boj#gold#bfs#dijkstra#shortest-path#graph
아카이브로 돌아가기

문제 링크

문제

크기가 1x1인 정사각형으로 나누어진 WxH 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.

'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.

레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '')을 설치해서 방향을 90도 회전시킬 수 있다.

아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.

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

입력

첫째 줄에 W와 H가 주어진다. (1 <= W, H <= 100)

둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.

  • .: 빈 칸
  • *: 벽
  • C: 레이저로 연결해야 하는 칸

'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.

출력

첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

풀이

이 문제는 거울 설치와 거의 같은 유형이다. 핵심은 한 칸에 도착했는지만 보는 것이 아니라 어떤 방향으로 그 칸에 도착했는지도 함께 상태로 관리해야 한다는 점이다.

하지만 차이점은 모든 칸에서 거울 설치를 고려해야 한다는 점이다. 그래서 상태를 (x, y, direction)으로 두고 각 상태까지 도달할 때 사용한 거울 수의 최솟값을 기록해야 한다. 직진은 비용이 그대로이고 좌회전이나 우회전은 거울 하나를 설치한 것과 같으므로 비용이 1 증가한다.

현재 코드에서는 dist[x][y][d]에 해당 방향으로 그 칸에 도착했을 때의 최소 거울 수를 저장하고 queue를 사용해 상태를 전파한다. 현재 방향으로 한 칸 전진한 뒤, 그대로 가는 경우는 비용 증가 없이 넣고 좌우로 꺾는 경우는 비용을 1 늘려서 함께 갱신한다.

참고로 PriorityQueue를 사용해서도 제출해볼 수 있지만 오히려 메모리를 더 먹을 수 있다. 이 문제에서는 방향별 최소 거울 개수만 잘 관리하면 일반 큐 기반 전개로도 충분했고, 핵심은 “모든 칸에서 꺾을 수 있다”는 점을 상태 전이로 빠짐없이 반영하는 것이다.

코드

cpp
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
 
int W, H;
char graph[100][100];
int dist[100][100][4];
pair<int, int> s, e;
 
const int INF = 1e9;
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
 
struct Node {
	int x, y, d, c;
};
 
int solve() {
	queue<Node> q;
	for (int i = 0; i < 4; i++) {
		q.push({ s.first, s.second, i, 0 });
		dist[s.first][s.second][i] = 0;
	}
 
	int ans = INF;
	while (!q.empty()) {
		Node cur = q.front();
		q.pop();
 
		if (cur.x == e.first && cur.y == e.second) {
			ans = min(ans, cur.c);
			continue;
		}
 
		if (dist[cur.x][cur.y][cur.d] < cur.c) continue;
 
		int nx = cur.x + dx[cur.d];
		int ny = cur.y + dy[cur.d];
 
		if (nx >= 0 && ny >= 0 && nx < H && ny < W && graph[nx][ny] != '*') {
			if (dist[nx][ny][cur.d] > cur.c) {
				dist[nx][ny][cur.d] = cur.c;
				q.push({ nx, ny, cur.d, cur.c });
			}
 
			int nd1 = (cur.d + 1) % 4;
			int nd2 = (cur.d + 3) % 4;
			int nc = cur.c + 1;
 
			if (dist[nx][ny][nd1] > nc) {
				dist[nx][ny][nd1] = nc;
				q.push({ nx, ny, nd1, nc });
			}
 
			if (dist[nx][ny][nd2] > nc) {
				dist[nx][ny][nd2] = nc;
				q.push({ nx, ny, nd2, nc });
			}
		}
	}
 
	return ans;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> W >> H;
 
	bool flag = false;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> graph[i][j];
			if (graph[i][j] == 'C') {
				if (!flag) {
					s = make_pair(i, j);
					flag = true;
				}
				else {
					e = make_pair(i, j);
				}
			}
 
			for (int d = 0; d < 4; d++) {
				dist[i][j][d] = INF;
			}
		}
	}
 
	cout << solve() << '\n';
	
	return 0;
}

복잡도

  • 시간 복잡도: O(HW)O(HW)
  • 공간 복잡도: O(HW)O(HW)

마무리

겉보기에는 단순한 BFS처럼 보여도 실제로는 방향 상태를 함께 갖고 가야 하는 문제다. 거울 설치와 같은 감각으로 접근하되 모든 칸에서 꺾는 선택지를 열어두고 비용을 갱신한다는 점만 정확히 잡으면 된다.