백준 1194 c++ "달이 차오른다, 가자." -PlusUltraCode-

https://www.acmicpc.net/problem/1194

 

[필자 사고]

기본적인 탐색 알고리즘을 이용하여 푸는 문제이다.

이 문제만의 특이한 점은 비트마스킹 즉 현재 키를 가지고 있으면 on/off 를 수행하게 해주는 비트마스킹을 이용해야 된다는 점이다.

또한 이 문제를 풀면서 배운점은 visited를 2차원 배열로 선언하게 되면 방문했떤 지점을 어떻게 초기화 시킬지 고민이였는데 

3차원 배열로 선언하여 추가된 인덱스의 범위를 1<<6으로 설정하여 비트마스킹의 범위로 선정하게 되면 고민했떤 부분을 해결할 수 있게 된다. 아래는 소스코드 해설이다.

[코드 해설]

 

• Input 함수
  • Input 함수는 미로의 크기(N, M)와 미로 데이터를 입력받습니다.
  • 미로는 vector<vector<char>> 형태의 2차원 배열로 저장됩니다.
  • 입력 도중 시작 위치(0)를 찾아 변수 originX와 originY에 저장합니다.
  • visited 배열은 특정 위치와 열쇠 상태(bit)를 기준으로 방문 여부를 관리하며, 이를 초기화합니다.
• isInside 함수
  • 주어진 좌표가 미로의 범위 내에 있는지 확인합니다.
  • sero와 garo가 유효한 범위에 속하면 true, 그렇지 않으면 false를 반환합니다.
• isContinue 함수
  • 특정 위치가 이동 가능한지 확인합니다.
  • 좌표가 범위 밖이거나 이미 방문한 경우, 또는 해당 위치가 벽('#')일 경우 이동을 중단해야 하므로 true를 반환합니다.
• updateBit 함수
  • 현재 열쇠 상태(nowBit)를 갱신합니다.
  • 새로운 열쇠가 발견되었을 경우, 해당 열쇠에 해당하는 비트를 활성화합니다.
• haveKey 함수
  • 현재 열쇠 상태(nowBit)를 확인하여 특정 문의 열쇠를 소유하고 있는지 검사합니다.
  • 문에 대응하는 비트가 활성화된 경우 true를 반환합니다.
• BFS 함수
  • BFS(너비 우선 탐색)를 사용하여 미로를 탐색하며 최단 경로를 찾습니다.
  • queue<Node>를 사용하여 현재 위치(sero, garo), 이동 횟수(count), 열쇠 상태(bit)를 관리합니다.
  • 큐에서 현재 노드를 꺼내고, 다음 노드로 이동 가능한지 확인합니다:
    • 이동하려는 칸이 열쇠(a-f)라면 bit를 갱신합니다.
    • 이동하려는 칸이 문(A-F)라면 해당 문을 열 수 있는 열쇠를 가지고 있는지 확인합니다.
  • 다음 노드로 이동 가능한 경우, 큐에 삽입하고 방문 처리를 합니다.
  • 목표 위치('1')에 도달하면 이동 횟수를 출력하고 탐색을 종료합니다.
  • 목표 위치에 도달할 수 없으면 -1을 출력합니다.
• Game_Start 함수
  • Game_Start 함수는 BFS 탐색을 시작하는 역할을 합니다.
  • 시작 위치(originX, originY)에서 탐색을 시작합니다.
• main 함수
  • main 함수는 Input 함수로 데이터를 입력받고, Game_Start 함수로 게임을 실행합니다.
  • 입출력 속도를 높이기 위해 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)를 사용합니다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

struct Node {
	int sero;
	int garo;
	int count;
	int bit;
};
int dy[4] = { 0,-1,0,1 };
int dx[4] = { 1,0,-1,0 };

int N, M;
vector<vector<char>> arr;
bool visited[50][50][1 << 6];
int originX, originY;

void Input() {
	cin >> N >> M;
	arr.resize(N);
	for (int i = 0; i < N; i++) {
		arr[i].resize(M);
	}

	memset(visited, false, sizeof(visited));

	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		for (int k = 0; k < str.size(); k++) {
			arr[i][k] = str[k];

			if (str[k] == '0') {
				originX = i;
				originY = k;
			}
		}
	}
}

bool isInside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
	return false;
}
bool isContinue(int sero, int garo, int bit) {
	if (isInside(sero, garo) == false)return true;
	if (visited[sero][garo][bit] == true)return true;
	if (arr[sero][garo] == '#') return true;

	return false;
}

int updateBit(int nowBit, char ch) {
	return nowBit | (1 << (ch - 'a'));
}
bool haveKey(int nowBit, char ch) {
	int checkBit = 1 << (ch - 'A');
	if ((nowBit & checkBit) == checkBit)return true;
	return false;
}

void BFS(int sero, int garo) {
	queue<Node> myQueue;
	myQueue.push({ sero,garo,0,0 });
	visited[sero][garo][0];

	while (!myQueue.empty()) {
		int nowSero = myQueue.front().sero;
		int nowGaro = myQueue.front().garo;
		int nowCount = myQueue.front().count;
		int nowBit = myQueue.front().bit;

		myQueue.pop();

		if (arr[nowSero][nowGaro] == '1') {
			cout << nowCount;
			return;
		}

		for (int i = 0; i < 4; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];
			int nextBit = nowBit;

			if (isContinue(nextSero, nextGaro, nowBit) == true) continue;
			if (arr[nextSero][nextGaro] >= 'a' && arr[nextSero][nextGaro] <= 'f') {
				nextBit = updateBit(nowBit, arr[nextSero][nextGaro]);
			}
			if (arr[nextSero][nextGaro] >= 'A' && arr[nextSero][nextGaro] <= 'F') {
				if (haveKey(nowBit, arr[nextSero][nextGaro]) == false)continue;
			}
			
			myQueue.push({ nextSero,nextGaro,nowCount + 1,nextBit });
			visited[nextSero][nextGaro][nextBit] = true;
		}

	}

	cout << -1;
	return;
}


void Game_Start() {
	BFS(originX, originY);

}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	Input();
	Game_Start();
}