[Java] BOJ15683, 백준 - 감시

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

15683번: 감시

 

시뮬레이션 문제이다.

주어진 순서대로 찹찹 구현하면 된다.

시뮬레이션 치고 생각할게 많아서 좀 복잡했다.

 

CCTV의 최대 개수가 8개이기때문에, CCTV의 모든 방향의 경우의 수를 탐색한다고 하더라도

4^8 = 65만

맵의 크기도 최대 64이기때문에 브루트 포스로 찾아도 시간은 충분하다고 본다.

 

*구현 순서*

1. CCTV의 위치를 찾아서 저장한다.

 

2. CCTV의 가능한 방향을 계산한다.

  1번: 상, 하, 좌, 우 네 방향 가능

  2번: 상/하, 좌/우 두 방향 가능

  3번: 상/우, 우/하, 하/좌, 좌/상 네 방향 가능

  4번: 상우하, 우하좌, 하좌상, 좌상우 네 방향 가능

  5번: 상하좌우 한 방향 가능

3번과 4번의 경우에 시계방향으로 방향이 변화하기 때문에 델타 배열 또한 상하좌우 순서대로 설정해주었음

private static final int[][] move = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };

방향 구하기의 전체 소스코드는 아래와 같다.

조합 구할때를 조금 응용하면 된다.

// cctv의 방향 설정하는 메서드
private static void setDir(int cnt) {
	if (cnt >= cctv) {
	// 영역 구하기
	check = new boolean[n][m];
	getDir();
	min = Math.min(min, getArea());
	return;
	}

	char c = map[cctvs[cnt].i][cctvs[cnt].j];
	if (c == '5') {
		// 5 -> 상하좌우
		setDir(cnt + 1);
	} else if (c == '2') {
		// 2 -> 상하/좌우
		for (int i = 0; i < 2; i++) {
			dir[cnt] = i;
			setDir(cnt + 1);
			dir[cnt] = 0;
		}
	} else {
		// 그 외: 모드 네개
		for (int i = 0; i < 4; i++) {
			dir[cnt] = i;
			setDir(cnt + 1);
			dir[cnt] = 0;
		}
	}
} // end setDir()

 

3. 방향을 다 정했다면 지정된 감시카메라의 방향대로 감시를 진행한다.

	private static void getDir() {
		// dir 배열이랑, cctvs 배열 가지고 진행하면 됨
		for (int i = 0; i < cctv; i++) {
			int cci = cctvs[i].i;
			int ccj = cctvs[i].j;
			int cctvNum = map[cci][ccj] - '0';
			switch (cctvNum) {
			case 1:
				monitor(cci, ccj, dir[i]);
				break;
			case 2:
				// 상하: 0,2 좌우: 1,3
				monitor(cci, ccj, dir[i] % 2);
				monitor(cci, ccj, dir[i] % 2 + 2);
				break;
			case 3:
				// 상우, 우하, 하좌, 좌상
				// 01, 12, 23, 30
				monitor(cci, ccj, dir[i]);
				monitor(cci, ccj, (dir[i] + 1) % 4);
				break;
			case 4:
				// 012, 123, 230, 301
				monitor(cci, ccj, dir[i]);
				monitor(cci, ccj, (dir[i] + 1) % 4);
				monitor(cci, ccj, (dir[i] + 2) % 4);
				break;
			case 5:
				// 0123
				monitor(cci, ccj, 0);
				monitor(cci, ccj, 1);
				monitor(cci, ccj, 2);
				monitor(cci, ccj, 3);
				break;
			}
		}
	} // end getDir()

위 소스코드는 직관적으로 생각한 그대로 구현했기 때문에 이해 자체는 쉽지만, 반복되는 부분이 많기때문에 아래와 같이 줄일 수 있다.

	private static void getDir() {
		// dir /cctvs 배열 가지고 진행
		for (int i = 0; i < cctv; i++) {
			int cci = cctvs[i].i;
			int ccj = cctvs[i].j;
			int cctvNum = map[cci][ccj] - '0';
			monitor(cci, ccj, dir[i]);
			if (cctvNum == 2)
				monitor(cci, ccj, dir[i] % 2 + 2);
			else
				for (int j = 1; j < cctvNum - 1; j++)
					monitor(cci, ccj, (dir[i] + j) % 4);

		}
	} // end getDir()

 

4. 체크한 CCTV 영역을 바탕으로 감시 사각지대 영역을 체크해주기만 하면 끝

 

 

<전체 소스코드>

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

public class Main {

	private static final int[][] move = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
	private static int n, m, cctv, min = Integer.MAX_VALUE;
	private static int[] dir;
	private static char[][] map;
	private static boolean[][] check;
	private static Point[] cctvs;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = parse(st.nextToken());
		m = parse(st.nextToken());

		map = new char[n][m];
		cctvs = new Point[8];
		cctv = 0;
		for (int i = 0; i < n; i++) {
			map[i] = br.readLine().replaceAll(" ", "").toCharArray();
			for (int j = 0; j < m; j++) {
				if (map[i][j] != '6' && map[i][j] != '0')
					// CCTV가 있는 곳
					cctvs[cctv++] = new Point(i, j);
			}
		} // end Input
		dir = new int[cctv];
		setDir(0);

		System.out.println(min);
	} // end main()

	// cctv의 방향 설정하는 메서드
	private static void setDir(int cnt) {
		if (cnt >= cctv) {
			// 영역 구하기
			check = new boolean[n][m];
			getDir();
			min = Math.min(min, getArea());
			return;
		}

		char c = map[cctvs[cnt].i][cctvs[cnt].j];
		if (c == '5') {
			// 5 -> 상하좌우
			setDir(cnt + 1);
		} else if (c == '2') {
			// 2 -> 상하/좌우
			for (int i = 0; i < 2; i++) {
				dir[cnt] = i;
				setDir(cnt + 1);
				dir[cnt] = 0;
			}
		} else {
			// 그 외: 모드 네개
			for (int i = 0; i < 4; i++) {
				dir[cnt] = i;
				setDir(cnt + 1);
				dir[cnt] = 0;
			}
		}
	} // end setDir()

	private static void getDir() {
		// dir /cctvs 배열 가지고 진행
		for (int i = 0; i < cctv; i++) {
			int cci = cctvs[i].i;
			int ccj = cctvs[i].j;
			int cctvNum = map[cci][ccj] - '0';
			monitor(cci, ccj, dir[i]);
			if (cctvNum == 2)
				monitor(cci, ccj, dir[i] % 2 + 2);
			else
				for (int j = 1; j < cctvNum - 1; j++)
					monitor(cci, ccj, (dir[i] + j) % 4);

		}
	} // end getDir()

	// 사각지대 수 구하기
	private static int getArea() {
		int ans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++)
				if (!check[i][j] && map[i][j] != '6')
					ans++;
		}
		return ans;
	} // end getArea()

	private static void monitor(int i, int j, int mode) {
		// 해당 점(i,j)으로부터 어떤 방향으로 감시를 계속하냐?
		while (i >= 0 && j >= 0 && i < n && j < m && map[i][j] != '6') {
			check[i][j] = true;
			i += move[mode][0];
			j += move[mode][1];
		}
	} // end monitor()

	private static int parse(String s) {
		return Integer.parseInt(s);
	}

	static class Point {
		int i, j;

		Point(int i, int j) {
			this.i = i;
			this.j = j;
		}
	}
}