백준 6087 - 레이저 통신(C++)

문제 링크입니다. https://www.acmicpc.net/problem/6087

6087번: 레이저 통신

BFS와 Dp를 사용해 풀었습니다.

두개의 C를 연결하는데 필요한 거울의 최소 갯수를 구하는 문제입니다.

먼저 거울을 설치했을 경우 레이저가 거울에 따라서 이동 방향이 달라집니다.

 

하지만 상하좌우 어느 방향에서 레이저가 들어오더라도 레이저의 방향이 대각선으로 변하는 경우는 없기에 이동 방향은 상하좌우만 신경쓰면 됩니다.

 

상하좌우만 신경쓰면 거울의 설치 갯수도 구하기 쉽습니다.

한쪽의 C에서 다른 쪽의 C까지 가는데 이동 방향이 몇번 바뀌었는지를 생각하면 됩니다. 

예제 1번을 확인하면 C에서 C까지 가는데 (아래, 오른쪽, 위쪽, 오른쪽)의 방향으로 이동했습니다.

이 경우, 처음 레이저가 아래에서 출발했다고 생각하면 거울은 3개만 필요한 셈입니다.

따라서 이동 방향이 몇번 바뀌었는지가 필요한 거울의 갯수가 되는겁니다.

 

그렇다면 레이저가 (X,Y) 좌표에 도달했을 경우, 각각 도달했을 때의 방향이 다를 수 있습니다.

방향을 신경써야하는 문제임으로 같은 좌표에 도달했더라도 이동 방향이 다르다면 다른 경우라고 생각해야합니다.

(X,Y) -> (X,Y+1)의 좌표로 이동해야 했을때, 방향에 따라 거울의 필요 여부가 달라지기 때문입니다.

따라서 2차원 배열이 아닌 방향까지 저장할 수 있는 3차원 배열을 사용해야됩니다.

 

저는 3차원 배열을 2개 만들었는데, 각각 "해당 좌표에 도착했는지", "해당 좌표로 오는데 방향을 몇번 바꿨는지" 입니다.

배열을 하나만 선언해도 될 것 같지만, 배열을 하나만 사용한다면 오류가 생깁니다.

한방향으로만 와서 해당 좌표의 배열 값이 0인데, 이를 이전에 방문하지 않았다고 생각하는 오류가 생길 수 있습니다.

저는 이를 피하기 위해 편한 방법인 배열을 2개 만들었습니다.

따라서 check배열에는 방문 여부와 raser배열에는 이동 방향의 변경 횟수가 저장되어 있습니다.

 

이전에 방문했던 위치라고 다시 방문하야하는 경우가 있습니다.

(X,Y) 좌표에 도달했을 때, Z번을 바꿔서 왔을 때, 해당 좌표가 이전에 방문했던 곳이라도 이번의 값이 더 작으면 바꾸는 것이 맞기 때문입니다. 따라서 해당 경우에는 좌표를 다시 queue에 넣어주면 됩니다.

 

탐색이 끝났다면 4방향에서 C까지 도달했을 때 필요한 최소 이동 방향을 저장할 수 있습니다.

마지막으로는 4방향 중, 가장 작은 값을 가져오면 되는 문제입니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#define P pair<int,int>
#define PP pair<P,int>
#define LL long long

using namespace std;

char map[101][101];
int check[101][101][4];
int raser[101][101][4];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int W, H;
P start, finish;

void bfs(P X){
	queue<PP> q; // 좌표 , 방향
	q.push({X, -1});
	for(int i = 0; i < 4; i++){
		check[X.first][X.second][i] = 1;
		raser[X.first][X.second][i] = 0;
	}
	while(!q.empty()){
		int x = q.front().first.first;
		int y = q.front().first.second;
		int dir = q.front().second;
		q.pop();
		for(int i = 0; i < 4; i++){
			int xx = x + dx[i];
			int yy = y + dy[i];
			if(xx >= 1 && xx <= H && yy >= 1 && yy <= W){
				if(map[xx][yy] == '*') continue;
				if(dir == i){
					if(check[xx][yy][i] == 0){
						raser[xx][yy][i] = raser[x][y][dir];
						check[xx][yy][i] = 1;
						q.push({{xx,yy}, i});
					}
					else{
						if(raser[xx][yy][i] > raser[x][y][dir]){
							raser[xx][yy][i] = raser[x][y][dir];
							q.push({{xx,yy},i});
						}
					}
				}
				else{
					if(check[xx][yy][i] == 0){
						raser[xx][yy][i] = raser[x][y][dir] + 1;
						check[xx][yy][i] = 1;
						q.push({{xx,yy}, i});
					}
					else{
						if(raser[xx][yy][i] > raser[x][y][dir] + 1){
							raser[xx][yy][i] = raser[x][y][dir] + 1;
							q.push({{xx,yy},i});
						}
					}
				}	
			}
		}
	}
}

void solve(){
	bfs(start);
	int mini = 100000001;
	for(int i = 0; i < 4; i++){
		if(check[finish.first][finish.second][i] == 0) continue;
		mini = min(mini, raser[finish.first][finish.second][i]);
	}
	cout << mini-1;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> W >> H;
	for(int i= 1; i <= H; i++){
		for(int j = 1; j <= W; j++){
			cin >> map[i][j];
			if(map[i][j] == 'C' && start.first == 0) start = {i,j};
			else if(map[i][j] == 'C') finish = {i,j};
		}
	}
	solve();
	return 0;
}

 

질문 및 조언은 댓글 남겨주세요