BOJ 14502 - 연구소

Problem Solving/그래프

Vjerksen 2017. 7. 12. 16:36

문제 링크

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

문제 해결

1. DFS를 이용해서 문제 해결. 0과 2의 row, column 인덱스를 저장하고 3중 for문을 활용해서 문제 해결.

주의할 점 || 생각해볼 점

참고

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

	/*
	explanation in vjerksen.tistory.com
	*/
	#include<cstdio>
	#include<iostream>
	#include<string>
	#include<algorithm>
	#include<cstring>
	#include<set>
	#include<stack>
	#include<map>
	#include<cmath>
	#include<queue>
	#include<cstdlib>
	#include<vector>
	#include<list>
	using namespace std;
	int N,M;
	int ans;
	int row_move[]={0,0,-1,1};
	int col_move[]={-1,1,0,0};
	vector<pair<int,int> > zero,two;
	int a[10][10],b[10][10];

	void dfs(int row,int col){
	for(int i=0;i<4;i++){
	int nrow=row+row_move[i];
	int ncol=col+col_move[i];
	if(nrow>=0&&nrow<N&&ncol>=0&&ncol<M){
	if(b[nrow][ncol]==0){
	b[nrow][ncol]=2;
	dfs(nrow,ncol);
	}

	}
	}
	}
	int main(){
	cin >> N >> M;
	for(int i=0;i<N;i++){
	for(int j=0;j<M;j++){
	scanf("%d",&a[i][j]);
	if(a[i][j]==2)
	two.push_back({i,j});
	else if(a[i][j]==0)
	zero.push_back({i,j});
	}
	}
	for(int i=0;i<zero.size();i++){
	for(int j=i+1;j<zero.size();j++){
	for(int k=j+1;k<zero.size();k++){
	memcpy(b,a,sizeof(a));
	b[zero[i].first][zero[i].second]=1;
	b[zero[j].first][zero[j].second]=1;
	b[zero[k].first][zero[k].second]=1;
	for(int l=0;l<two.size();l++){
	dfs(two[l].first,two[l].second);
	}
	int cnt=0;
	for(int x=0;x<N;x++){
	for(int y=0;y<M;y++){
	if(b[x][y]==0)
	cnt++;
	}
	}
	ans=max(ans,cnt);
	}
	}
	}
	printf("%d",ans);
	return 0;
	}