BOJ 6087번: 레이저 통신

문제

문제 바로가기> BOJ 6087번: 레이저 통신

6087번: 레이저 통신

 

풀이

한 단계 더 발전한 BFS 느낌이었다.

핵심은 4차원 방문 배열 + Prioirty Queue 이용이다. 

💡 최단 거리가 아닌, 최소로 거울을 활용하는 횟수를 구하므로,
Priority Queue를 이용하여 가장 적은 거울이 필요한 경우부터 탐색해주었다.

💡 visited[y][x][before_dir][next_dir]
: 위치 (y, x) , 이전 방향 before_dir , 다음 방향 next_dir

 

처음에 3차원을 방문 배열을 이용해서 문제를 풀려고 했다.

visited[y][x][dir] : 위치 (y, x) , 방향 dir

 

그런데 다음 예시를 봐보자.

이 예시의 정답은 (0,0) 위치에 거울이 하나만 사용되면 되기 때문에 1이다.

하지만, 이미 해당 방향으로, 도착한 적이 있다면? 그런데 그게 다른 방향에서 온 거라면?

더 적은 거울을 사용할 수 있음에도, 이미 방문처리가 되어있어서 더 적은 거울을 활용할 수 없다.

따라서 4차원 방문 배열을 이용해 주었다.

💡 ex) 초기 pq
{0 3 0 0}
{0 3 2 0}
{0 3 3 0}
{0 3 1 0}

💡 {0 3 0 0} 에서의 4방향 탐색
{1 3 1 1}
: 실제로는 거울 개수 0개로 방문 가능. ( {0 3 1 0}에서 방문하는 경우 )
  하지만, {0 3 0 0} 에서 방문 처리하는 경우 1개가 필요

{0 2 2 1}
: 실제로는 거울 개수 0개로 방문 가능. ( {0 3 2 0}에서 방문하는 경우 )
  하지만, {0 3 0 0} 에서 방문 처리하는 경우 1개가 필요

 

 

#include<iostream>
#include<string>
#include<queue>
#define MAX 101
using namespace std;

// 위치 (y, x), 이전방향, 거울 수
struct DATA { 
	int y, x, bd, cnt;
	bool operator < (const DATA &D) const {
		return cnt > D.cnt; // min heap
	}
};

int W, H;
int sy, sx;
char map[MAX][MAX];
bool visited[MAX][MAX][4][4];
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };

void input() {
	cin >> W >> H;

	string line;
	bool isfind = false; // C 한개만 저장하기 위해
	for (int i = 0; i < H; i++) {
		cin >> line;
		for (int j = 0; j < W; j++) {
			map[i][j] = line[j];
			if (map[i][j] == 'C' && !isfind) {
				isfind = true;
				map[i][j] = '.';
				sy = i; sx = j; // 시작 위치 저장
			}
		}
	}
}

int solution() { // 설치해야 하는 거울 개수의 최솟값
	
	// 가장 적은 거울이 필요한 경우부터 살펴보기 위해
	priority_queue<DATA> pq;
	for (int nd = 0; nd < 4; nd++) {
		pq.push({sy, sx, nd, 0});
		visited[sy][sx][nd][nd] = true;
	}

	while (!pq.empty()) {
		int y = pq.top().y;
		int x = pq.top().x;
		int bd = pq.top().bd;
		int cnt = pq.top().cnt;
		pq.pop();

		if (map[y][x] == 'C') return cnt;

		for (int nd = 0; nd < 4; nd++) {
			int ny = y + dy[nd];
			int nx = x + dx[nd];
			if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue; // 범위를 벗어나는 경우
			if (map[ny][nx]=='*' || visited[ny][nx][bd][nd]) continue; // 벽인 경우, 이미 방문한 경우
			visited[ny][nx][bd][nd] = true;
			if (nd != bd) pq.push({ ny,nx, nd, cnt + 1 });
			else pq.push({ ny,nx, nd, cnt});
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	input();
	cout << solution();
}