[백준(Baekjoon)][자바(java)] [삼성 SW 역량 테스트 기출 문제] 15683 : 감시

 

www.acmicpc.net/problem/15683

15683번: 감시

 

문제 풀이

 

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

public class Main {

	static class CCTV {
		int x, y, t;  // x, y, type
		CCTV( int x, int y, int t ) {
			this.x = x;
			this.y = y;
			this.t = t;
		}
	}
	
	static int[] dx = { -1, 0, 1, 0 }, dy = { 0, 1, 0, -1 };  // up right down left ( clockwise )
	static int n, m, o[][], c, em;  // o : office map, c : num of cctv. em : min num of empty cell
	static List<CCTV> cctv;  // cctv list ( coordinate, type )
	
	public static void copyMap( int a[][], int a_c[][] ) {
		int x, y;
		for( x = 0; x < n; ++x )
			for( y = 0; y < m; ++y )
				a_c[x][y] = a[x][y];
	}
	
	public static void watchCCTV( int x, int y, int d ) {
		d %= 4;
		int nx = x, ny = y;
		while( true ) {
			nx += dx[d];
			ny += dy[d];
			if( nx < 0 || nx >= n || ny < 0 || ny >= m || o[nx][ny] == 6 ) 
				break;
			if( o[nx][ny] == 0 )
				o[nx][ny] = -1;
		}
	}
	
	public static void backtrack( int i ) {
		int x, y;
		if( i == c ) {
			int e = 0;
			for( x = 0; x < n; ++x )
				for( y = 0; y < m; ++y )
					if( o[x][y] == 0 )
						e++;
			em = em > e ? e : em;
			return;
		}
		CCTV ct = cctv.get(i);
		int t = ct.t, s = t == 1 ? 2 : 4;
		x = ct.x; y = ct.y;
		int o_c[][] = new int[n][m];  // office map copy
		for( int d = 0; d < s; ++d ) {
			copyMap( o, o_c );
			watchCCTV( x, y, d );
			switch( t ) {
			case 1:
				watchCCTV( x, y, d+2 );
				break;
			case 2:
				watchCCTV( x, y, d+1 );
				break;
			case 3:
				watchCCTV( x, y, d+1 );
				watchCCTV( x, y, d+2 );
				break;
			}
			backtrack( i + 1 );
			copyMap( o_c, o );
		}
	}
	
	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() );
		o = new int[n][m];
		em = Integer.MAX_VALUE;
		cctv = new ArrayList<>();
		int x, y, t;
		for( x = 0; x < n; ++x ) {
			st = new StringTokenizer( br.readLine() );
			for( y = 0; y < m; ++y ) {
				t = Integer.parseInt( st.nextToken() );
				o[x][y] = t;
				if( t >= 1 && t <= 4 )
					cctv.add( new CCTV( x, y, t-1 ) );  // type 1씩 빼서 취급
			}
		}
		br.close();

		c = cctv.size();

		for( x = 0; x < n; ++x )
			for( y = 0; y < m; ++y )
				if( o[x][y] == 5 )
					for( d = 0; d < 4; ++d )
						watchCCTV( x, y, d );

		backtrack( 0 );
		
		System.out.println( em );
	}
}

 

*  크기가 n x m인 사무실 지도( o : office )를 입력받음 ( int o[][] )

*  사무실 지도의 값 설명

*  CCTV의 위치( x, y ), 종류( t : type )를 담은 class 생성 ( int x, y, t )

*  숫자가 1 ~ 4일 경우 CCTV 이므로 리스트에 추가 ( List<CCTV> cctv ) -- 종류 번호는 1 뺌
 ( CCTV 5는 방향 조합 따지기 전에 미리 감시 가능 칸(-1)으로 표시할 것이므로 굳이 리스트에 넣지 않음 )

*  방향( d : direction ) 순서  ( => 시계방향 )

*  cctv 번호별 감시 범위
 ( cctv 번호( t : type )는 0 <= t < 5 ( 1씩 빼서 취급 ) )
 ( 현재 방향으로부터 x° 회전된 방향도 감시 가능한지 )

( 4번 cctv는 4방향 모두 감시 가능하므로 조합 따질 필요 없이 무조건 4방향 감시 )

*  cctv들의 개수( c : num of cctv ) 만큼 backtracking 하여
   각 cctv별로 방향을 회전 해가며 얻을 수 있는 조합의 경우의 수를 따져가며 감시를 하고
   감시 되지 않은 빈 칸( 0 )의 개수( e : num of empty cell )를 구해 최솟값( em : min 〃)을 구함