백준 1194 - 달이 차오른다, 가자.(C++)

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

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

비트마스킹을 사용한 구현 문제였습니다.

비트마스킹이라는 방법을 사용하는 문제였습니다.

int 형 변수를 비트연산자처럼 사용하는 방법인데, 0과 1을 이용해 원하는 데이터 값을 저장합니다.

예를 들어, 문제에서 열쇠를 a, c, f를 가지고 있다면, 10101로 나타내 해당 위치의 열쇠를 가지고 있는지 저장합니다.

 

그렇다면 새로운 열쇠를 얻었을 때, 저장하는 방법은 어떤 연산자를 사용하면 가능할까요?

비트 연산자에는 AND / OR연산자가 있습니다.

AND는 비교하는 두 수가 모두 1이라면 1, 아니면 0을 가지게 됩니다.

OR는 비교하는 두 수 중, 하나만 1을 가지고 있다면 1을 가지게 됩니다. 

열쇠를 얻는 거는 새로운 값을 추가하는 것임으로 이전에 해당 열쇠를 가지고 있는지 확인할 필요가 없습니다.

따라서, OR 연산자를 사용해서 추가해주면 됩니다.

int N_key = Key | (1 << (int(map[xx][yy] - 'a')));

해당 방법을 통해, 이전의 Key 값에서 새로 얻은 키 값을 추가해주면 됩니다.

 

그렇다면 문을 열때는 AND를 사용하면 될 것입니다.

int ans = Key & (1 << (int(x - 'A')));
 if(ans != 0) return true;
 else return false;

가지고 있는 열쇠와 현재 열어야 할 문을 비교해, 열쇠를 가지고 있으면 문을 여는 방식으로 코드가 짜여졌습니다.

 

 

마지막으로 주의할 것은, 이전에 방문한 점을 기록하는 방법을 다르게 해야합니다.

check배열을 통해 (X, Y)좌표에 방문 했는지를 저장했습니다. 

하지만 (X, Y)좌표를 방문했을 때, a~f까지 총 2^6의 경우의 수를 가지고 방문할 수 있습니다.

따라서 [N][M][1 << 6]의 방법으로 가지고 있는 열쇠의 경우를 모두 확인해줘야합니다.

 

 

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

#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 LL long long
#define pp pair<int, int>
#define P pair<pp, pp>
#define F first
#define S second
#define INF 987654321

using namespace std;

int N, M;
char map[51][51];
int check[51][51][1 << 6];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
pp start;

bool have_key(char x, int Key){
    int ans = Key & (1 << (int(x - 'A')));
    if(ans != 0) return true;
    else return false;
}

int bfs(){
    queue<P> q;
    q.push({start, {0, 0}});
    check[start.F][start.S][0] = 1;
    while(!q.empty()){
        int x = q.front().F.F;
        int y = q.front().F.S;
        int cnt = q.front().S.F;
        int Key = q.front().S.S;
        q.pop();
        if(map[x][y] == '1') return cnt;
        for(int i = 0; i < 4; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx >= 1 && xx <= N && yy >= 1 && yy <= M){
                if(check[xx][yy][Key] == 1) continue;
                if(map[xx][yy] == '.' || map[xx][yy] == '1'){
                    check[xx][yy][Key] = 1;
                    q.push({{xx, yy}, {cnt + 1, Key}});
                }
                else if(map[xx][yy] >= 'a' && map[xx][yy] <= 'f'){
                    int N_key = Key | (1 << (int(map[xx][yy] - 'a')));
                    check[xx][yy][N_key] = 1;
                    q.push({{xx, yy}, {cnt + 1, N_key}});
                }
                else if(map[xx][yy] >= 'A' && map[xx][yy] <= 'F'){
                    if(have_key(map[xx][yy], Key)){
                        check[xx][yy][Key] = 1;
                        q.push({{xx, yy}, {cnt + 1, Key}});
                    }
                }
            }
        }
    }
    return -1;
}

void solve(){
    int ans = bfs();
    cout << ans;
}

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

 

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