[BOJ] 1194:달이 차오른다, 가자.

 

0. 문제

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

1194번: 달이 차오른다, 가자.

 

1. 문제 분석

이 문제는 우선 그리드가 주어지고, 조건을 만족하기 위한 이동 횟수의 최솟값(최단 경로)를 찾는다는 점에서 BFS 알고리즘을 이용해 문제를 풀어야 한다. 

 

2. 유의할 점

- 각각 여섯 개의 키를 가지거나 혹은 가지고 있지 못하거나, 이 모든 상황(2^6=64)에 대해 체크해 주어야 한다. 이를 위해 vtd(방문여부 확인 배열)을 3차원으로 구현해야 하고, BFS를 위한 queue에 넣을 자료구조도 x, y 값 뿐 아니라 key 값에 대한 정보도 가지고 있어야 한다.

- vtd에서 세번째 차원의 index(0 ~ 63)를 6개의 열쇠를 가지고 있는지 여부를 쉽게 알 수 있는 형태로 변환해주어야 한다. 이를 위해서 아래 코드에서는 int 형의 index를 string으로 변환해서 열쇠를 가지고 있는지 확인하거나 해당 열쇠를 얻은 상태를 갱신해주는 데에 사용했다.

 

3. 소스 코드(C++)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#define endl '\n'
#define INF 987654321
using namespace std;

typedef pair<int, int> ii;

struct node {
	int y, x, k;
	node(int ty, int tx, int tk) {
		y = ty;
		x = tx;
		k = tk;
	}
};

int n, m;
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
char grid[52][52];
bool vtd[52][52][64];
queue<node> q;

// a  b  c  d  e  f
// 1  2  4  8  16 32

int bi_to_dec(string bi) {
	int dec = 0, tmp = 1;
	for (int i = 0; i < bi.size(); i++) {
		dec += tmp * (bi[i] - '0');
		tmp *= 2;
	}
	return dec;
}

string dec_to_bi (int dec) {
	string bi = "";
	while (dec > 0) {
		if (dec == 1){
			bi += '1';
			break;
		}
		char tmp = (dec % 2) + ' 0';
		bi += tmp;
		dec /= 2;
	}
	while (bi.size() < 6) bi += '0';
	return bi;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	bool flag = false;
	int mov = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> grid[i][j];
			if (grid[i][j] == '0') {
				q.push(node(i, j, 0));
				vtd[i][j][0] = true;
			}
		}
	}
	while (!q.empty() && !flag) {
		int s = q.size();
		mov++;
		while (s--) {
			int yy = q.front().y;
			int xx = q.front().x;
			int kk = q.front().k;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int ny = yy + dy[i];
				int nx = xx + dx[i];
				if (vtd[ny][nx][kk] || !grid[ny][nx] || grid[ny][nx] == '#')
                	continue;
				string sk = dec_to_bi(kk);
				if (grid[ny][nx] >= 'A' && grid[ny][nx] <= 'F') {
					if (sk[grid[ny][nx] - 'A'] == '0') continue;
					q.push({ ny,nx,kk });
					vtd[ny][nx][kk] = true;
				}
				else {
					if (grid[ny][nx] == '1') {
						flag = true;
						break;
					}
					if (grid[ny][nx] >= 'a' && grid[ny][nx] <= 'f') {
						sk[grid[ny][nx] - 'a'] = '1';
						int kkk = bi_to_dec(sk);
						q.push({ ny,nx,kkk });
						vtd[ny][nx][kkk] = true;
					}
					else {
						q.push({ ny,nx,kk });
						vtd[ny][nx][kk] = true;
					}
				}
			}
			if (flag) break;
		}
	}
	if (flag) cout << mov;
	else cout << -1;
	return 0;
}

 

 

4. 여담

- string으로 풀어낸 key를 그냥 int 형으로 표현해도 10^6이므로, string이 아니라 그냥 int 형 그대로 사용해 조작하는 방법도 있다.

- vtd 배열에 위치 뿐 아니라 다른 속성의 상황까지도 표현해야 한다는 점에서 [BOJ_2206]벽 부수고 이동하기와 구현 방식이 비슷하다.