[백준 14502] 연구소(JAVA/C++)

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

14502번: 연구소

 

이전에 C++로 풀었던 문제이다. JAVA로 다시 풀어보았다.

map 입력 받을 때 벽을 세울 수 있는 공간이면 ArrayList(C++은 Vector)에 넣어주었다.

벽을 최대 3개까지 세울 수 있기때문에 3중포문을 돌려서 벽을 3개 세워주고, 바이러스를 퍼뜨려서 안전영역 갯수를 카운트해줬다.

 

[JAVA]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N,M,ans=0;
	static int[][] map;
	static boolean[][] visit;
	static int[] dx= {0,0,1,-1};
	static int[] dy= {1,-1,0,0};
	static ArrayList<int[]> list=new ArrayList<int[]>();
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine()," ");
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		map=new int[N][M];
		
		for(int i=0; i<N; i++) {
			st=new StringTokenizer(br.readLine()," ");
			for(int j=0; j<M; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
				if(map[i][j]==0) list.add(new int[] {i,j});
			}
		}
        
		//벽세우기
		for(int i=0; i<list.size()-2; i++) {
			for(int j=i+1; j<list.size()-1; j++) {
				for(int z=j+1; z<list.size(); z++) {
					visit=new boolean[N][M];
					int[] arr_i=list.get(i);
					int[] arr_j=list.get(j);
					int[] arr_z=list.get(z);
					map[arr_i[0]][arr_i[1]]=1;
					map[arr_j[0]][arr_j[1]]=1;
					map[arr_z[0]][arr_z[1]]=1;
					spread();//퍼뜨리기
					map[arr_i[0]][arr_i[1]]=0;
					map[arr_j[0]][arr_j[1]]=0;
					map[arr_z[0]][arr_z[1]]=0;
				}
			}
		}
		System.out.println(ans);
		

	}
	private static void spread() {
		int cnt=0;//안전영역
		int[][] temp=new int[N][M];
		mapCopy(temp,map);
		Queue<int[]> q=new LinkedList<int[]>();
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j]==2) {
					visit[i][j]=true;
					q.offer(new int[] {i,j});
				}
			}
		}
		while(!q.isEmpty()) {
			int[] a=q.poll();
			int x=a[0];
			int y=a[1];
			for(int i=0; i<4; i++) {
				int nx=x+dx[i];
				int ny=y+dy[i];
				if(nx<0||ny<0||nx>=N||ny>=M||visit[nx][ny]==true
						||map[nx][ny]==1)continue;
				map[nx][ny]=2;
				visit[nx][ny]=true;
				q.offer(new int[] {nx,ny});
			}
		}
		//안전영역 세기
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j]==0)cnt++;
			}
		}
		if(ans<cnt) {
			ans=cnt;
		}
		mapCopy(map,temp);
	}
	private static void mapCopy(int[][] a1, int[][] a2) {
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				a1[i][j]=a2[i][j];
			}
		}
	}
	

}

 

 

[C++]

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, M;
int map[8][8],ans=0;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
vector <pair<int, int> > v;

void Spread(){
	int cmap[8][8];
	bool visited[8][8] = { 0 };
	queue <pair<int, int> > q;
	for (int i = 0; i < N; i++)for (int j = 0; j < M; j++) {
		cmap[i][j] = map[i][j];
	}
	for (int i = 0; i < N; i++)for (int j = 0; j < M; j++) {
		if (cmap[i][j] == 2 && visited[i][j]==0) {
			visited[i][j] = true;
			q.push({ i,j });
			while (!q.empty()) {
				int x = q.front().first;
				int y = q.front().second;
				q.pop();
				for (int d = 0; d < 4; d++) {
					int nx = x + dx[d];
					int ny = y + dy[d];
					if (nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny] || cmap[nx][ny]==1)
						continue;
					visited[nx][ny] = true;
					cmap[nx][ny] = 2;
					q.push({ nx,ny });
				}
			}
		}
	}
	int cnt = 0;
	for (int i = 0; i < N; i++)for (int j = 0; j < M; j++) {
		if (cmap[i][j] == 0) cnt++;
	}
	if (cnt > ans) ans = cnt;

}
void Wall(int i, int j, int z) {
	map[v[i].first][v[i].second] = 1;
	map[v[j].first][v[j].second] = 1;
	map[v[z].first][v[z].second] = 1;
	Spread();
	map[v[i].first][v[i].second] = 0;
	map[v[j].first][v[j].second] = 0;
	map[v[z].first][v[z].second] = 0;
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++)for (int j = 0; j < M; j++) {
		cin >> map[i][j];
		if (map[i][j] == 0) v.push_back({ i,j });
	}
	for (int i = 0; i < v.size()-2; i++) {
		for (int j = i + 1; j < v.size()-1; j++) {
			for (int z = j + 1; z < v.size(); z++) {
				Wall(i, j, z);
			}
		}
	}
	cout << ans;
	return 0;
}