[백준(Baekjoon)][자바(java)] [삼성 SW 역량 테스트 기출 문제] 14502 : 연구소

 

www.acmicpc.net/problem/14502

14502번: 연구소

 

문제 풀이

import java.io.*;
import java.util.*;

public class Main {
	
	static class Cell {
		int x, y;
		Cell( int x, int y ) {
			this.x = x;
			this.y = y;
		}
	}
	
	static int[] dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 };
	static int n, m, map[][], es, ea, sa_max;  // es : empty size, ea : empty area, sa_max : safe area max 
	static List<Cell> ec, vc;  // ec : empty cells, vc : virus cells

	public static void com( int k, int l, int a[], boolean v[] ) {
		if( k == 3 ) {
			int map_c[][] = new int[n][m], i, j, nx, ny, sa, va = 0;  Cell c;  // map_c : map copy, nx/y : next x/y, sa : safe area, va : viral area 
			for( i = 0; i < n; ++i ) 
				for( j = 0; j < m; ++j )
					map_c[i][j] = map[i][j];
			for( i = 0; i < 3; ++i ) {
				c = ec.get( a[i] );
				map_c[c.x][c.y] = 1;
			}
			boolean vis[][] = new boolean[n][m];
			Queue<Cell> q = new ArrayDeque<>();
			for( Cell cc : vc )
				q.add( new Cell( cc.x, cc.y ) );
			while( !q.isEmpty() ) {
				c = q.remove();
				for( i = 0; i < 4; ++i ) {
					nx = c.x + dx[i];
					ny = c.y + dy[i];
					if( nx < 0 || nx >= n || ny < 0 || ny >= m )
						continue;
					if( !vis[nx][ny] && map_c[nx][ny] == 0 ) {
						q.add( new Cell( nx, ny ) );
						vis[nx][ny] = true;
						va++;
					}
				}
			}
			sa = ea - va;
			sa_max = sa_max < sa ? sa : sa_max;
			return;
		}
		for( int i = l; i < es; i++ ) {
			if( !v[i] ) {
				v[i] = true;
				a[k] = i;
				com( k+1, i+1, a, v );
				v[i] = false;
			}
		}
	}

	public static void main(String[] args) throws IOException {
		
		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];
		ec = new ArrayList<>();
		vc = new ArrayList<>();
		int i, j, t;
		for( i = 0; i < n; ++i ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < m; ++j ) {
				t = Integer.parseInt( st.nextToken() );
				map[i][j] = t;
				if( t == 0 )
					ec.add( new Cell( i, j ) );
				if( t == 2 )
					vc.add( new Cell( i, j ) );
			}
		}
		br.close();
		
		es = ec.size();
		ea = es - 3;
		com( 0, 0, new int[es], new boolean[es] );
		
		System.out.println( sa_max );
	}
}

*  한 칸의 x, y 좌표 값으로 구성된 Cell class 생성

*  지도( int map[][] )의 값들을 입력받을 때, 빈 칸( ec : empty cells ), 바이러스 칸( vc : virus cells )들을 각각 List<Cell> ec, vc 에 담음

*  빈 칸들 중 3 곳에 벽을 세울 것이므로 후에 빈 영역( ea : empty area )은 빈 칸들의 개수( es : empty size ) - 3 과 같다

*  빈 칸들의 개수( es : empty size ) 중 3개를 뽑는 조합( com() )을 구함
-  map[][] 값들을 복사하여 map_c[][] 배열에 옮겨 담고, 3개의 빈 칸을 벽으로 바꿈
-  Queue<Cell>에 바이러스 칸들을 넣고, BFS하며 바이러스가 퍼진 영역( va : virus area )( 원래의 바이러스 위치 제외 ) 구함

*  안전한 영역( sa : safe area )은 빈 영역에서 바이러스가 퍼진 영역을 뺀 값이다.
   조합의 경우의 수들 중 가장 큰 안전한 영역( sa_max )을 구해 출력