[백준 1194] 달이 차오른다, 가자

홍시홍 2020. 1. 9. 23:35

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

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

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.

www.acmicpc.net

요구사항

그래프에서 목적지까지 최소 이동 거리 구하기 bfs

풀이

기본적인 bfs + 비트마스크 문제이다.

key를 가지고 있는가 없는가를 비트 마스크를 이용하여 처리한다.

visit[r]][c]에 비트마스크 배열을 추가해준다

visit[r][c][bitmask]

#include <iostream>
#include <queue>

using namespace std;
struct go {
	int x;
	int y;
	int key;
	int cnt;
};
int n, m;
char map[51][51];
int visit[51][51][1 << 6];
int sr, sc;
int dc[4] = { 0,-1,0,1 };
int dr[4] = { -1,0,1,0 };
int main()
{

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf(" %c", &map[i][j]);
			if (map[i][j] == '0') {
				sr = i;
				sc = j;
			}
		}
	}
	queue<go> q;
	q.push({ sr,sc,0 ,0});
	int flag = 0;
	int ans = 0;
	while (!q.empty()) {
		int r = q.front().x;
		int c = q.front().y;
		int key = q.front().key;
		int cnt = q.front().cnt;
	//	cout << r << " " << c << endl;
		if (map[r][c] == '1') {
			//cout << "AA" << endl;
			//cout << cnt << endl;
			flag = 1;
			ans = cnt;
			break;
		}
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nr = r + dr[i];
			int nc = c + dc[i];
			if (nr < 0 || nc < 0 || nr >= n || nc >= m) {
				continue;
			}
			if (map[nr][nc] == '#')
				continue;
			if (visit[nr][nc][key] == 1)
				continue;
			if (map[nr][nc] == 'A' || map[nr][nc] == 'B' || map[nr][nc] == 'C' || map[nr][nc] == 'D' || map[nr][nc] == 'E' || map[nr][nc] == 'F')
			{
				//cout << "ASDF" << endl;
				int nowNum = (int)map[nr][nc] - 'A';
				bool nkey = (key & (1<<nowNum));
				//cout << "nkey"<<nkey << endl;
				if (nkey == 1) {
					visit[nr][nc][key] = 1;
					q.push({ nr,nc,key,cnt+1 });
				}
			}
			if (map[nr][nc] == 'a' || map[nr][nc] == 'b' || map[nr][nc] == 'c' || map[nr][nc] == 'd' || map[nr][nc] == 'e' || map[nr][nc] == 'f') {
				//cout << "A" << endl;
				int nowNum = (int)map[nr][nc] - 'a';
				int nkey = (key | (1 << nowNum));
				//visit[nr][nc][key] = 1;
				visit[nr][nc][nkey] = 1;
				q.push({ nr,nc,nkey,cnt + 1 });
			}
			if (map[nr][nc] == '0' || map[nr][nc] == '.' || map[nr][nc]=='1')
			{
				visit[nr][nc][key] = 1;
				q.push({ nr,nc,key,cnt + 1 });
			}
		}
	}
	
	if (flag == 1)
		cout << ans << endl;
	else {
		cout << "-1" << endl;
	}
}