BOJ 17141 연구소 2

백준 17141 링크

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

17141번: 연구소 2

풀이

순열을 이용해서 바이러스를 배치하는 경우의 수를 갈라주고 따지고 각각의 경우에서 BFS를 돌려주면 끝?(아마) 순열은 DFS로 구했음.

 

자대에 오고 사지방에서 처음으로 풀어보는 문제였음. 거의 4개월만에 푸는거라 감각을 다시 익히고 하는데 힘들었음. (Dev 말고 VS 쓸 수 있으면 좋겠다) 동기에게 백준을 알려주고 몇몇 문제를 추천해 주었다. 이상 전달끝.

코드

#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;

int n,m,o_map[52][52], t_map[52][52],v_avail[10][2], v_count;
int v_select[10][2];
int min2=0x7fffffff, cannot_reach;
int xl[] = {0,0,-1,1};
int yl[] = {1,-1,0,0};
queue < pair<int,int> > q;

//room where never visited is marked -1
//wall is makred -2
//virus start point is 0

int boundary_check(int x, int y){
	if(1<=x&&x<=n&&1<=y&&y<=n&&t_map[x][y]==-1)
		return 1;
	else
		return 0;
}

void set_tempmap(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			t_map[i][j]=o_map[i][j];
		}
	}
	for(int i=0;i<m;i++){
		t_map[v_select[i][0]][v_select[i][1]]=0;
		q.push({v_select[i][0],v_select[i][1]});
	}
}

void sim_start(){
	int x, y, nx, ny, max, reach;
	reach = 0;
	max=0;
	while(!q.empty()){
		x=q.front().first;
		y=q.front().second;
		q.pop();
		for(int i=0;i<4;i++){
			nx=x+xl[i];
			ny=y+yl[i];
			if(boundary_check(nx,ny)){
				t_map[nx][ny]=t_map[x][y]+1;
				max = t_map[nx][ny]>max?t_map[nx][ny]:max;
				q.push({nx,ny});
			}
		}
	}
	//check if there is place never visited
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(t_map[i][j] == -1){
				max = 0x7fffffff;
			}
		}
	}
	min2 = max<min2?max:min2;
}

void DFS(int idx, int cnt){
	if(cnt == m){
		set_tempmap();
		sim_start();
	}
	else{
		if(idx==v_count){
			return;
		}
		else{
			DFS(idx+1,cnt);
			v_select[cnt][0]=v_avail[idx][0];
			v_select[cnt][1]=v_avail[idx][1];
			DFS(idx+1,cnt+1);
		}
	}
}

int main() {
	//freopen("input.txt","r",stdin);
	
	scanf("%d %d",&n,&m);
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%d", &o_map[i][j]);
			if(o_map[i][j] == 0){
				o_map[i][j] = -1;
			}
			else if(o_map[i][j] == 1){
				o_map[i][j] = -2;
			}
			else if(o_map[i][j] == 2){
				v_avail[v_count][0]=i;
				v_avail[v_count++][1]=j;
				o_map[i][j] = -1;
			}
		}
	}
	
	DFS(0,0);
	
	if(min2==0x7fffffff){
		cout<<-1;
	}
	else{
		cout<<min2;
	}
}