백준 2151 - 거울 설치(C++)

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

2151번: 거울 설치

다차원 배열을 이용한 BFS로 풀 수 있는 문제였습니다.

두 개의 문이 있을 때, 거울을 이용해 한쪽 문에서 다른 문을 볼 수 있도록 할려고 한다면 몇개의 거울을 사용해야되는지 구하는 문제입니다.

먼저 2개의 문의 위치를 저장한 뒤, 한 쪽 거울에서 BFS 탐색을 시작해줍니다.

여기서는 거울의 설치 갯수를 물어보는 문제이니,
배열 하나를 만들어 큰 값을 저장해줍니다.
그러면서, 탐색이 진행될 때마다 해당 배열의 값을 해당 좌표까지 가기 위해서 필요한 거울의 갯수로 저장을 할 것입니다.
주의할 점은, 방향은 4방향으로 갈 수 있기 때문에, 해당 방향을 의미하는 칸까지 만들어서 값을 저장해줘야 합니다.

이 다음은 탐색을 하기 위한 초기 값을 찾는 과정입니다.
먼저 두 개의 문 중, 하나의 문을 선택합니다. 해당 문에서 갈 수 있는 방향을 찾은 뒤, {좌표와 방향, 0(지금까지 필요한 거울의 갯수)}를 queue에 넣어줍니다.

그 다음, 해당 좌표에서 갈 수 있는 방향으로 한 칸 이동했다면,
1. 해당 좌표가 map 범위를 넘지 않아야 한다.
2. 갈 수 있는 곳이여야 한다.
-> 2가지 경우를 모두 만족해야 합니다.

2가지 경우도 만족했다면, 갈 수 있는 경우가 2가지 있습니다.
1. 거울을 설치 할 수 있는 여부
   ->가는 방향이 좌, 우라면 2가지 방향(상, 하)로 변경 가능합니다. 이 반대 또한 성립합니다.
       이때는, 거울을 설치한 것이기에 거울 갯수를 하나 늘려줍니다.
2. 원래 방향으로 한 칸 전진 -> 이 경우는 거울을 설치할 필요가 없습니다. 따라서 그냥 전진해주면 됩니다.
--> 2가지 경우 모두, 이동하려는 칸에 저장된 값과 비교해야합니다. 만약 이동하려는 칸에 저장된 값이 더 작다면 이동할 필요가 없기 때문입니다.

탐색이 모두 끝났다면, 남은 문의 좌표에서 4방향에 저장된 값 중, 가장 작은 값을 출력합니다.


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

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#define INF 987654321
#define F first
#define S second

using namespace std;

int N;
char map[51][51];
int Distance[51][51][4];
vector<pair<int, int>> door, mirror;
int dx[4] = {1, 0, -1, 0}; // 우, 하, 좌, 상
int dy[4] = {0, 1, 0, -1};

void reset_distance(){
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			for(int k = 0; k < 4; k++){
				Distance[i][j][k] = INF;
			}
		}
	}
}

void find_distance(pair<int, int> st){
	reset_distance();
	queue<pair<pair<int, int>, pair<int, int>>> q; //좌표, 방향, 거울 갯수
	for(int i = 0; i < 4; i++){
		int x = st.F + dx[i];
		int y = st.S + dy[i];
		Distance[st.F][st.S][i] = 0;
		if(x >= 1 && x <= N && y >= 1 && y <= N){
			if(map[x][y] == '*') continue;
			q.push({{st}, {i, 0}}); // 갈 수 있는 방향을 저장
		}
	}
	while(!q.empty()){
		int x = q.front().F.F;
		int y = q.front().F.S;
		int way = q.front().S.F;
		int cnt = q.front().S.S;
		q.pop();
		int xx = x + dx[way];
		int yy = y + dy[way];
		if(xx < 1 || xx > N || yy < 1 || yy > N) continue; // 해당 좌표가 map 범위를 넘어서면 continue
		if(map[xx][yy] == '*') continue; //갈 수 없는 곳이면 continue
		if(map[xx][yy] == '!'){ //만약 거울을 설치할 수 있는 곳이라면
			if(way == 0 || way == 2){ // 방향이 우, 좌일때는 상, 하로 바꿀 수 있다.
				if(Distance[xx][yy][1] > cnt + 1){ // 거울 설치 갯수를 비교 후
					Distance[xx][yy][1] = cnt + 1;
					q.push({{xx, yy}, {1, cnt+1}});
				}
				if(Distance[xx][yy][3] > cnt + 1){
					Distance[xx][yy][3] = cnt + 1;
					q.push({{xx, yy}, {3, cnt+1}});
				}
			}
			else{
				if(Distance[xx][yy][0] > cnt + 1){
					Distance[xx][yy][0] = cnt + 1;
					q.push({{xx, yy}, {0, cnt+1}});
				}
				if(Distance[xx][yy][2] > cnt + 1){
					Distance[xx][yy][2] = cnt + 1;
					q.push({{xx, yy}, {2, cnt+1}});
				}
			}
		}
		if(Distance[xx][yy][way] > cnt){ // 어떤 경우든 원래 방향대로 한 칸을 갈 수 있다.
			Distance[xx][yy][way] = cnt;
			q.push({{xx, yy}, {way, cnt}});
		}
	}
}

void solve(){
	find_distance(door[0]);
	int ans = INF;
	for(int i = 0; i < 4; i++){
		ans = min(ans, Distance[door[1].F][door[1].S][i]);
	}
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			cin >> map[i][j];
			if(map[i][j] == '#') door.push_back({i, j});
		}
	}
	solve();
	return 0;
}

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