BOJ 1194 - 달이 차오른다, 가자.

문제 링크

---

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

문제 해결

---

1. 기본적인 BFS에 비트마스크를 추가한 형태로 해결. visit[row][column][key_bitmask]

주의할 점

---

1. 같은 시간대를 구현하기 위해서 큐의 크기를 이용.

	/*
	explanation in vjerksen.tistory.com
	*/
	#include<cstdio>
	#include<cstdlib>
	#include<iostream>
	#include<string>
	#include<deque>
	#include<vector>
	#include<algorithm>
	#include<queue>
	#include<set>
	#include<cmath>
	using namespace std;
	int N,M,s_row,s_col,ans;
	int row_move[]={0,0,-1,1};
	int col_move[]={-1,1,0,0};
	char miro[55][55];
	bool visit[55][55][65]; // row,col,key
	bool flag;
	void bfs(int row, int col){
	queue<pair<pair<int, int>,int> > q;
	visit[row][col][0]=true;
	q.push({{row,col},0});
	while(!q.empty()){
	// caution 1
	int q_size = q.size();
	while(q_size--){
	int c_row = q.front().first.first;
	int c_col = q.front().first.second;
	int c_key = q.front().second;
	if(miro[c_row][c_col] == '1'){
	flag = true;
	return;
	}
	q.pop();
	for(int i=0;i<4;i++){
	int n_row = c_row+row_move[i];
	int n_col = c_col+col_move[i];
	int n_key = c_key;
	if(n_row<0||n_row>=N||n_col<0||n_col>=M)
	continue;
	if(miro[n_row][n_col]=='#')
	continue;
	if(miro[n_row][n_col]>='a'&&miro[n_row][n_col]<='f'){
	n_key |= (1 << (miro[n_row][n_col]-'a'));
	}
	if(miro[n_row][n_col]>='A'&&miro[n_row][n_col]<='F'){
	if(!(n_key & (1 << (miro[n_row][n_col]-'A'))))
	continue;
	}
	if(!visit[n_row][n_col][n_key]){
	visit[n_row][n_col][n_key]=true;
	q.push({{n_row,n_col},n_key});
	}
	}
	}
	ans++;
	}
	}
	int main(){
	scanf("%d %d\n",&N,&M);
	for(int i=0;i<N;i++){
	scanf("%s",miro[i]);
	for(int j=0;j<M;j++){
	if(miro[i][j] == '0'){
	s_row = i;
	s_col = j;
	}
	}
	}
	bfs(s_row,s_col);
	if(flag) printf("%d",ans);
	else puts("-1");
	return 0;
	}

view raw BOJ 1194.cpp hosted with ❤ by GitHub

※ 정확하고 부드러운 태클은 언제나 환영입니다.