백준_14502 연구소(자바) / 조합 + dfs

시간 & 메모리 제한

문제

입력

출력

문제 풀이

package com.Back;

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


public class Back_14502 {

	static int row,col;
	static int map1[][];
	//원본을 바꾸지 않기 위한 복사본
	static int map2[][];
	static boolean visited[][];
	static int dx[]= {-1,1,0,0};
	static int dy[]= {0,0,-1,1};
	
	static int ans=0;
	
	//바이러스 위치
	static ArrayList<point> virus= new ArrayList<>(); 

	
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		col = Integer.parseInt(st.nextToken());
		row = Integer.parseInt(st.nextToken());
		map1 = new int[col][row];
		map2 = new int[col][row];
		visited = new boolean[col][row];
		
		for (int i = 0; i < col; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < row; j++) {
				map1[i][j]=Integer.parseInt(st.nextToken());
				if(map1[i][j]==2) {
					virus.add(new point(i, j));
				}
			}
		}
		combi(0);
		System.out.println(ans);
		
	}
	private static void combi(int cnt) {
		if(cnt==3) {

			for (int i = 0; i < col	; i++) {
				for (int j = 0; j < row; j++) {
					map2[i][j]=map1[i][j];
				}
			}
		
			for (int i = 0; i < virus.size(); i++) {
				dfs(virus.get(i).x,virus.get(i).y);
			}
			
			int temp=0;
			for (int i = 0; i < col; i++) {
				for (int j = 0; j < row; j++) {
					if(map2[i][j]==0) {
						temp++;
					}
				}
			}
			ans = temp>ans?temp:ans;
			return;
		}
		for (int i = 0; i < col; i++) {
			for (int j = 0; j < row; j++) {
				if(map1[i][j]==0) {
					map1[i][j]=1;
					combi(cnt+1);
					map1[i][j]=0;
				}
			}
		}
	}
	private static void dfs(int x, int y) {
		for (int k = 0; k < 4; k++) {
			int xx = x + dx[k];
			int yy = y + dy[k];
			if (xx >= 0 && xx < col && yy >= 0 && yy < row && map2[xx][yy] == 0) {
				map2[xx][yy] = 2;
				dfs(xx,yy);
			}
		}
	}
	static class point{
		int x;
		int y;
		public point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
		
	}
}

Combination + dfs 문제

 

- step1 입력을 받을 때 바이러스는 ArrayList로 따로 빼서 진행을 합니다.

 

- step2 조합을 combination 을 이용해서 벽을 세울 3곳을 지정합니다.

 

- step3 지정이 끝나면 조건문을 통해서 빠져 나오게 만들고, map[][]에 대한 복사본을 만듭니다.

 

- step4 dfs를 통해서 카피본map에 2를 퍼뜨립니다.

 

- step5 0의 갯수를 세고 비교 과정을 통해서 가장 넓은 0의 갯수를 답으로 선택합니다.