백준 14502 연구소 C++

백준  14502번 연구소 C++.

백준 14502번 "연구소" 문제의 자세한 내용은 글 하단의 문제 링크를 참고하세요.

14502번 문제에 주어지는 입력 및 예시

입력: 

7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

출력:

27

코드

백준 14502번 "연구소" 문제의 코드입니다.

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> virus,wall;
int n,m,result,tmp;
int a[8][8],visited[8][8];
int dx[4]={0, 1, 0, -1}; 
int dy[4]={-1, 0, 1, 0}; //위오아왼 
void dfs(int y,int x){
	visited[y][x]=1;
    for(int i=0;i<4;i++){
        int _dx=dx[i]+x;
        int _dy=dy[i]+y;
        if(_dy<0 || _dx<0 || _dy>=n || _dx>= m ) continue;
		if( visited[_dy][_dx]==1 || a[_dy][_dx]==1 ) continue;   
        dfs(_dy,_dx);
    }
    return;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            cin>>a[i][j];
            if(a[i][j]==0) wall.push_back({i,j});
            if(a[i][j]==2) virus.push_back({i,j});
        }
    for(int i=0;i<wall.size();i++){
        for(int j=0;j<i;j++){
            for(int k=0;k<j;k++){
            	fill(&visited[0][0],&visited[0][0]+8*8,0);
            	tmp=0;
                a[wall[i].first][wall[i].second]=1;
                a[wall[j].first][wall[j].second]=1;
                a[wall[k].first][wall[k].second]=1; 
    			for(pair<int,int>v:virus)
        			dfs(v.first,v.second);
    			for(int ii=0;ii<n;ii++)
        			for(int jj=0;jj<m;jj++)
            			if(a[ii][jj]==0&&visited[ii][jj]==0) tmp++;
                result=result>tmp?result:tmp;
                a[wall[i].first][wall[i].second]=0;
                a[wall[j].first][wall[j].second]=0;
                a[wall[k].first][wall[k].second]=0;
            }
        }    
	}
    cout<<result;
    return 0;
}

실행

위의 코드를 예제의 입력을 넣어 실행했을 때의 결과입니다.

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

14502번: 연구소