백준 15683 감시 - 삼성 SW 역량 테스트 기출

백준 15683 감시 - 삼성 SW 역량 테스트 기출

1. 문제 링크

https://www.acmicpc.net/problem/15683

15683번: 감시

 

2. 문제 해결에 대한 아이디어

1. CCTV의 종류는 총 5개가 있으며 사각 지대를 최소로 만들기 위해 각 CCTV의 방향을 돌려서 조사해야한다.

2. 회전에 따라 감시할 수 있는 영역이 달라지는 케이스는 각 CCTV 별로 아래와 같다.

   . 1번 - 4 / 2번 - 2 / 3번 - 4 / 4번 - 4 / 5번 - 1

3. input을 받을 때 CCTV 객체를 생성하여 cctvList에 add했다.

4. 재귀로 각 cctv의 케이스를 적용하여 사각지대를 구한다.

5. 회전에 따른 케이스 조사는 CCTV 객체에 저장된 r(회전수) 만큼 진행했고 회전할 때마다 방향을 90도씩 회전했다.

 

3. 코드

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

public class Main {
	static class CCTV {
		int no, y, x, r;

		public CCTV(int no, int y, int x, int r) {
			super();
			this.no = no;
			this.y = y;
			this.x = x;
			this.r = r;

		}

	}

	static int N, M; // N * M 보드
	static int[] dirY = { 1, 0, -1, 0 }; // 북 0 동 1 남 2 서 3
	static int[] dirX = { 0, 1, 0, -1 };
	static int[][] board;
	static int answer = Integer.MAX_VALUE;
	static ArrayList<CCTV> cctvList = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] nm = br.readLine().split(" ");
		N = Integer.parseInt(nm[0]);
		M = Integer.parseInt(nm[1]);
		board = new int[N][M];

		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split(" ");
			for (int j = 0; j < M; j++) {
				board[i][j] = Integer.parseInt(line[j]);
				if (board[i][j] != 6 && board[i][j] != 0) {
					int no = board[i][j];
					int rotateNum = 0;
					if (no == 2)
						rotateNum = 2;
					else if (no == 5)
						rotateNum = 1;
					else
						rotateNum = 4;
					cctvList.add(new CCTV(no, i, j, rotateNum)); 
				}
			}
		}

		allCase(0);
		System.out.println(answer);

	}

	static void allCase(int depth) {
		if (depth == cctvList.size()) {
			getBlindSize();
			return;
		}

		CCTV c = cctvList.get(depth);
		int y = c.y;
		int x = c.x;
		int d = 0;
		for (int j = 0; j < c.r; j++) {
			int[][] copy = new int[N][M];
			toCopy(copy);
			if (c.no == 1) {
				marking(y, x, d);
			} else if (c.no == 2) {
				marking(y, x, d);
				marking(y, x, (d + 2) % 4);
			} else if (c.no == 3) {
				marking(y, x, d);
				marking(y, x, (d + 1) % 4);
			} else if (c.no == 4) {
				marking(y, x, d);
				marking(y, x, (d + 1) % 4);
				marking(y, x, (d + 2) % 4);
			} else {
				marking(y, x, d);
				marking(y, x, (d + 1) % 4);
				marking(y, x, (d + 2) % 4);
				marking(y, x, (d + 3) % 4);
			}
			allCase(depth + 1);
			d = (d + 1) % 4;
			toOrigin(copy);
		}

	}

	static void toOrigin(int[][] copy) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				board[i][j] = copy[i][j];
			}
		}
	}

	static void toCopy(int[][] copy) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				copy[i][j] = board[i][j];
			}
		}
	}

	static void marking(int y, int x, int d) {
		while (true) {
			y = y + dirY[d];
			x = x + dirX[d];

			if (y < 0 || x < 0 || y >= N || x >= M || board[y][x] == 6)
				break;

			if (board[y][x] == 0) // 빈칸인 경우에만 마킹, CCTV는 통과
				board[y][x] = -1;
		}
	}

	static void getBlindSize() {
		int sum = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (board[i][j] == 0)
					++sum;
			}
		}
		answer = Math.min(answer, sum);
	}
}

 

4. 채점 결과

 

5. 느낀 점

1. 시험장에서 못 풀었던 문제였는데.. 왜 못 풀었을까 싶다.