[백준][자바][14502]연구소

이 문제를 풀면서 2가지의 문제점을 찾았다

1. 문제를 제대로 안읽음

2. 조건처리를 제대로 안함 

사실 두번째는 첫번째의 하위 항목에 해당하는 것이긴 하지만..

대충 푸는데 2시간 정도 걸렸다(틀렸지만)

맨처음엔 안전영역중에 최대영역인줄알고 

dfs로 안전영역들을 찾아서 돌렸다

근데 알고보니 최대안전영역이였다...

그냥 간단하게 해결했다

이 문제는 완전탐색 문제였는데

나는 항상 완전탐색 문제에 루프문들을 짜다보면 

조금 시간초과가 걱정이된다...이부분은 내가 시간복잡도를 계산하는데 문제가 있다는 말이겠지.

로직은 크게 이런 로직을 따른다. 

1. 벽세우기

2. 바이러스 뿌리기

3. 안전영역 계산

4. 다시 되돌리기

5. 1로 돌아간다 

나는 1번 벽세우기가 조금 애로사항이였는데..ㅋㅋ 

다른 분들을 보니 dfs로 해결하더라.

다음 문제는 dfs문제를 풀어보려고한다.  조합같은거?

그리고 벽을 배열에서 꺼내오는데 안전영역에만 벽을 세울수 있게끔 처리를 안해서

...81%에서 계속 틀렸다. 밑에 조건문 하나만  넣으니 해결되었다...

아침에 일찍 카페에 들려서 해결하니 참 좋다.

 카페도 이쁘고...

이제..ㅠ 좀 있으면 일하러가야하는구만..ㅠ 오늘도 화팅해야겠다!

if( map[i][j] == 0) {

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/*
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 
2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
빈 칸의 개수는 3개 이상이다.
*/
class v_Point{
	
	int x; 
	int y; 
	
	v_Point(int y, int x){
		this.x = x;
		this.y = y;
	}
}
public class backjoon_14502_연구소 {
	static int[][] map = new int[9][9];
	static int[][] temp = new int[9][9];
	static boolean[][] visit = new boolean[9][9];
	
	static Queue
 vq = new LinkedList();
	static ArrayList vArr= new ArrayList(); 
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1}; 
	static int N;
	static int M;
	static int max_SafeZone = 0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		for (int i = 0 ; i < N; i++) {
			for(int j = 0; j < M; j++) {
				map[i][j] = sc.nextInt();
				temp[i][j] = map[i][j]; //맵 복사 
				//바이러스 위치 저장
				if( map[i][j] == 2) {
					vq.add(new v_Point(i,j));
				}
				// 좌표 어레이리스트 
				//0인 안전영역만 넣어야 0인곳 위치만 설치가능
				if( map[i][j] == 0) {
					vArr.add(new v_Point(i,j));
				}
			}
		}
		
		
		wall();
		//wall();
		System.out.println(max_SafeZone);
		
		
	}
	public static void cal_MaxSafeZone() {
		int cnt = 0;
		for(int i=0; i< N; i++) {
			for (int j = 0; j < M; j++) {
					//System.out.println(i +" " + j);
				if( map[i][j] == 0 ) {
					cnt += 1;
					//find_SafeZone(i,j,cnt);
				}
			}
		}
		if (max_SafeZone <= cnt) {
			max_SafeZone = cnt;
		}
	}
	
	//벽 세우기 
	public static void wall() {
		int vlen = vArr.size();
		for(int i = 0 ; i < vlen-2; i++) {
			for(int j = i+1; j < vlen-1; j++) {
				for(int k =j+1; k< vlen; k++) {
					v_Point first_Wall = vArr.get(i);
					v_Point second_Wall = vArr.get(j);
					v_Point third_Wall = vArr.get(k);
					map[first_Wall.y][first_Wall.x] = 1;
					map[second_Wall.y][second_Wall.x] = 1;
					map[third_Wall.y][third_Wall.x] = 1;
					
					//바이러스 돌리고 
					virus();
					//최대 안전영역 구하기
					cal_MaxSafeZone();				
					//printMap();
					//맵 초기화 
					returnMap();
				}
			}
		}
	}
	
	//맵 초기상태로 전환 
	public static void returnMap() {
		for(int i=0; i< N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j]=temp[i][j];
				if( map[i][j] == 2) {
					vq.add(new v_Point(i,j));
				}
			}
		}
	}
	
	
	public static void virus() {
		while(!vq.isEmpty()) {
			v_Point p = vq.poll();
			for(int i = 0; i < 4; i++) {
				int garo = dx[i] + p.x;
				int sero = dy[i] + p.y;
				if(garo >= 0 && garo < M && sero >=0 && sero < N) {
					if( map[sero][garo] == 0 ) {
						map[sero][garo] = 2;
						vq.add(new v_Point(sero, garo));
					}
				}
			}
		}
	}
	public static void printMap() {
		for(int i=0; i< N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}
}