백준 15683번-감시(JAVA)

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

15683번: 감시

 

 

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

public class observation {
	static int N, M;
	static int[][] map;
	static int[][] deltas = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
	static List<int[]> cctv = new ArrayList<int[]>();
	static int Min = Integer.MAX_VALUE;
	static int blind = 0;;

	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];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				// CCTV이면 cctv 리스트에 종류, 좌표 저장
				if (map[i][j] > 0 && map[i][j] < 6) {
					int[] e = new int[3];
					e[0] = map[i][j];
					e[1] = i;
					e[2] = j;
					cctv.add(e);
				}
				// map[i][j] == 0이면 감시전 영역 수++
				else if (map[i][j] == 0)
					blind++;
			}
		}
		permutation(0, new int[cctv.size()]);
		if (Min <= 0) {
			System.out.println(0);
			return;
		}
		System.out.println(Min);
	}

	// 중복 순열 뽑는 함수
	// cctv리스트에 들어있는 cctv들의 방향 중복 순열 뽑기
	private static void permutation(int toSelect, int[] selected) {
		if (toSelect == cctv.size()) {
			// 중복 순열을 뽑았으면 사각지대 수 계산 함수 호출
			calc(selected);
			return;
		}
		for (int i = 0; i < 4; i++) {
			selected[toSelect] = i;
			permutation(toSelect + 1, selected);
		}
	}

	// 사각지대 수 계산 함수
	private static void calc(int[] selected) {
		// 매개변수로 넘어온 방향 순열로 계산할 사각지대 수 temp를 blind로 초기화
		int temp = blind;
		// map 복제
		int[][] clone = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				clone[i][j] = map[i][j];
			}
		}
		// cctv의 List에 들어있는 순서대로
		for (int i = 0; i < cctv.size(); i++) {
			temp = observe(temp, cctv.get(i), selected[i], clone);
		}
		// 최소 사각지대 갱신
		if (Min > temp)
			Min = temp;
	}

	// cctv 감시 수행
	private static int observe(int temp, int[] cctv, int selected, int[][] cmap) {
		// cctv의 종류에 따라 수행
		switch (cctv[0]) {
		// 1방향
		case 1:
			int dx1 = cctv[1] + deltas[selected][0];
			int dy1 = cctv[2] + deltas[selected][1];
			while (dx1 >= 0 && dy1 >= 0 && dx1 < N && dy1 < M) {
				if (cmap[dx1][dy1] == 6)
					break;
				if (cmap[dx1][dy1] == 0) {
					temp--;
					cmap[dx1][dy1] = -1;
				}
				dx1 += deltas[selected][0];
				dy1 += deltas[selected][1];
			}
			break;
		// 반대 2방향
		case 2:
			int dx2 = cctv[1] + deltas[selected][0];
			int dy2 = cctv[2] + deltas[selected][1];
			while (dx2 >= 0 && dy2 >= 0 && dx2 < N && dy2 < M) {
				if (cmap[dx2][dy2] == 6)
					break;
				if (cmap[dx2][dy2] == 0) {
					temp--;
					cmap[dx2][dy2] = -1;
				}
				dx2 += deltas[selected][0];
				dy2 += deltas[selected][1];
			}
			// -deltas[selected];가 반대 방향
			dx2 = cctv[1] - deltas[selected][0];
			dy2 = cctv[2] - deltas[selected][1];
			while (dx2 >= 0 && dy2 >= 0 && dx2 < N && dy2 < M) {
				if (cmap[dx2][dy2] == 6)
					break;
				if (cmap[dx2][dy2] == 0) {
					temp--;
					cmap[dx2][dy2] = -1;
				}
				dx2 -= deltas[selected][0];
				dy2 -= deltas[selected][1];
			}
			break;
		// 직각방향
		case 3:
			int dx3 = cctv[1] + deltas[selected][0];
			int dy3 = cctv[2] + deltas[selected][1];
			while (dx3 >= 0 && dy3 >= 0 && dx3 < N && dy3 < M) {
				if (cmap[dx3][dy3] == 6)
					break;
				if (cmap[dx3][dy3] == 0) {
					temp--;
					cmap[dx3][dy3] = -1;
				}
				dx3 += deltas[selected][0];
				dy3 += deltas[selected][1];
			}
			//selected가 deltas의 마지막인 경우 다음 방향은 0
			if (selected == 3)
				selected = 0;
			//selected가 deltas의 마지막이 나닌 경우 다음 방향은 selected += 1
			else
				selected += 1;
			dx3 = cctv[1] + deltas[selected][0];
			dy3 = cctv[2] + deltas[selected][1];
			while (dx3 >= 0 && dy3 >= 0 && dx3 < N && dy3 < M) {
				if (cmap[dx3][dy3] == 6)
					break;
				if (cmap[dx3][dy3] == 0) {
					temp--;
					cmap[dx3][dy3] = -1;
				}
				dx3 += deltas[selected][0];
				dy3 += deltas[selected][1];
			}
			break;
		// 3방향
		case 4:
			for (int i = 0; i < 4; i++) {
				// 선택된 방향만 제외하고 3방향 탐색
				if (i == selected)
					continue;
				int dx4 = cctv[1] + deltas[i][0];
				int dy4 = cctv[2] + deltas[i][1];
				while (dx4 >= 0 && dy4 >= 0 && dx4 < N && dy4 < M) {
					if (cmap[dx4][dy4] == 6)
						break;
					if (cmap[dx4][dy4] == 0) {
						temp--;
						cmap[dx4][dy4] = -1;
					}
					dx4 += deltas[i][0];
					dy4 += deltas[i][1];
				}
			}
			break;

		case 5: // 4방향
			for (int i = 0; i < 4; i++) {
				int dx5 = cctv[1] + deltas[i][0];
				int dy5 = cctv[2] + deltas[i][1];
				while (dx5 >= 0 && dy5 >= 0 && dx5 < N && dy5 < M) {
					if (cmap[dx5][dy5] == 6)
						break;
					if (cmap[dx5][dy5] == 0) {
						temp--;
						cmap[dx5][dy5] = -1;
					}
					dx5 += deltas[i][0];
					dy5 += deltas[i][1];
				}
			}
			break;
		}
		return temp;
	}
}