[백준] [삼성 SW 역량 테스트 기출 문제] 15683. 감시 (JAVA)

👁‍🗨 감시

 

이지

 

---

문제

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.

 

 

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

 

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

 

CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.

 

 

CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 칸을 감시할 수 없다.

0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5

위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.

 

 

CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.

0 0 2 0 3
0 6 0 0 0
0 0 6 6 0
0 0 0 0 0

위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.

# # 2 # 3
0 6 # 0 #
0 0 6 6 #
0 0 0 0 #

 

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 세 정수 A, B, C가 주어진다.

 

출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

 

---

💡  나의 풀이

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Pos {
	int r;
	int c;

	Pos(int r, int c) {
		this.r = r;
		this.c = c;
	}
}

class Main {
	static int R;
	static int C;
	static int[][] map;
	static int[] caseNum = new int[] {0,4,2,4,4,1};
	static List<Pos> cam = new ArrayList<>();
	static int min = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new int[R][C];

		for(int r=0; r<R; r++) {
			st = new StringTokenizer(br.readLine());
			for(int c=0; c<C; c++) {
				map[r][c] = Integer.parseInt(st.nextToken());
				if(map[r][c] > 0 && map[r][c] < 6)
					cam.add(new Pos(r,c));
			}
		}
		dfs(0);
		System.out.println(min);
	}

	private static void dfs(int depth) {
		if(depth == cam.size()) {
			min = Math.min(min, countBlindSpot());
			return;
		}

		Pos cur = cam.get(depth);
		int camType = map[cur.r][cur.c];

		int[][] tmpMap = new int[R][C];
		copy(tmpMap, map);

		for(int i=0; i<caseNum[camType]; i++) {
			monitor(cur, i);
			dfs(depth+1);
			copy(map, tmpMap);
		}
	}

	private static void copy(int[][] arr1, int[][] arr2) {
		for(int r=0; r<R; r++) {
			arr1[r] = arr2[r].clone();
		}
	}

	private static int countBlindSpot() {
		int cnt = 0;
		for(int r=0; r<R; r++) {
			for(int c=0; c<C; c++) {
				if(map[r][c] == 0) cnt++;
			}
		}
		return cnt;
	}

	private static void monitor(Pos cam, int dir) {
		int camType = map[cam.r][cam.c];
		switch(camType) {
			case 1:
				camNumOne(cam, dir);
				break;
			case 2:
				camNumTwo(cam, dir);
				break;
			case 3:
				camNumThree(cam, dir);
				break;
			case 4:
				camNumFour(cam, dir);
				break;
			case 5:
				camNumFive(cam);
		}
	}

	private static void camNumOne(Pos cam, int dir) {
		switch(dir) {
			case 0: //상
				goUpward(cam);
				break;
			case 1: //하
				goDownward(cam);
				break;
			case 2: //좌
				goLeftward(cam);
				break;
			case 3: //우
				goRightward(cam);
				break;
		}
	}

	private static void camNumTwo(Pos cam, int dir) {
		switch(dir) {
			case 0: //상하
				goUpward(cam);
				goDownward(cam);
				break;
			case 1: //좌우
				goLeftward(cam);
				goRightward(cam);
				break;
		}
	}

	private static void camNumThree(Pos cam, int dir) {
		switch(dir) {
			case 0: //북동
				goUpward(cam);
				goRightward(cam);
				break;
			case 1: //동남
				goRightward(cam);
				goDownward(cam);
				break;
			case 2: //남서
				goDownward(cam);
				goLeftward(cam);
				break;
			case 3: //북서
				goLeftward(cam);
				goUpward(cam);
				break;
		}
	}

	private static void camNumFour(Pos cam, int dir) {
		switch(dir) {
			case 0: //ㅗ
				goLeftward(cam);
				goUpward(cam);
				goRightward(cam);
				break;
			case 1: //ㅏ
				goUpward(cam);
				goRightward(cam);
				goDownward(cam);
				break;
			case 2: //ㅜ
				goLeftward(cam);
				goDownward(cam);
				goRightward(cam);
				break;
			case 3: //ㅓ
				goDownward(cam);
				goLeftward(cam);
				goUpward(cam);
				break;
		}
	}
	private static void camNumFive(Pos cam) {
		goUpward(cam);
		goDownward(cam);
		goLeftward(cam);
		goRightward(cam);
	}

	private static void goUpward(Pos cam) {
		for(int r=cam.r-1; r>=0; r--) {
			if(map[r][cam.c] == 6) break;
			if(map[r][cam.c] == 0)
				map[r][cam.c] = -1;
		}
	}

	private static void goDownward(Pos cam) {
		for(int r=cam.r+1; r<R; r++) {
			if(map[r][cam.c] == 6) break;
			if(map[r][cam.c] == 0)
				map[r][cam.c] = -1;
		}
	}

	private static void goLeftward(Pos cam) {
		for(int c=cam.c-1; c>=0; c--) {
			if(map[cam.r][c] == 6) break;
			if(map[cam.r][c] == 0)
				map[cam.r][c] = -1;
		}
	}

	private static void goRightward(Pos cam) {
		for(int c=cam.c+1; c<C; c++) {
			if(map[cam.r][c] == 6) break;
			if(map[cam.r][c] == 0)
				map[cam.r][c] = -1;
		}
	}
}

 

DFS를 이용해 브루트포스 방법으로 모든 경우를 탐색했다. 

케이스를 잘 나눠서 메소드를 설계하면 어렵지 않게 해결할 수 있다.

 

 

---

 

15683번: 감시