[백준] 15683. 감시 - 골드5

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

15683번: 감시

 

문제 요약

원문 확인

 

문제 해결 아이디어

완전 탐색으로 해결했다.

먼저 cctv의 좌표를 다 배열에 저장해 두었다. cctv의 종류마다 회전할 수 있는 횟수가 정해져 있는데, 나올 수 있는 방향대로 다 cctv를 켜본 뒤에 사각 지대를 계산했다.

cctvControl 함수에 임시 배열을 매개변수로 호출하는데, 이렇게 하는 이유는 cctv를 켜보고 결과를 확인한 후에 다시 전의 상태로 돌려 놔야 다음 방향도 확인 할 수 있기 때문이다. 

결론적으로 흐름은 cctv마다 나올 수 있는 방향대로 반복문을 돌며 cctv를 켜고 다음 cctv를 뽑는 것을 반복한다.

모든 cctv를 다 켜봤으면 사각지대를 구하고 return한다. 이러면 반복문 안에 있기 때문에 다음 방향도 확인하고 다음 cctv를 확인할 수 있다. 결국 모든 경우를 구하는 것이다.

 

cctvControl로 전해지는 int형 변수 k는 cctv 종류마다 나올 수 있는 경우를 모두 구해서 그 경우마다 일일이 방향을 정해서 cctv를 켤 수 있게 하기 위한 변수이다. 예를 들어 1번 cctv는 상, 하, 좌, 우 총 네 가지의 경우가 주어지기 때문에 cctvControl에는 0부터 3까지의 k값이 전달될 수 있다. 그때마다 호출되는 함수가 다르다.

 

개선하고 싶은 점은 up down right left 함수로 cctv를 켜보는 시뮬레이션을 의도했는데, 구현하고 나니 방향만 다를 뿐 코드의 내용이 같아서 방향 배열이라든지 매개변수라든지 아무튼 구별할 수 있는 방법을 찾아서 하나의 함수로 합칠 수도 있을 것 같다.

 

완성된 코드

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

public class Main {
	/*
	 * 340ms
	 */
	
	static int N, M, cctvs[][], index, min;

	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());

		int[][] map = new int[N][M];

		cctvs = new int[8][2]; // cctv 위치 저장 배열. 최대 8개
		index = 0; // cctv 개수 기억해두는 인덱스

		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());
				if (map[i][j] >= 1 && map[i][j] <= 5) {
					cctvs[index][0] = i;
					cctvs[index][1] = j;
					index++;
				}
			}
		}

		min = Integer.MAX_VALUE;
		pick(0, map);
		System.out.println(min);
	}

	private static void pick(int cnt, int[][] map) {
		if (cnt == index) {
			int sum = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (map[i][j] == 0)
						sum++;
				}
			}
			min = Math.min(min, sum);
			return;
		}

		int r = cctvs[cnt][0];
		int c = cctvs[cnt][1];
		int info = map[r][c];

		// 감시
		// 1,3,4번 씨씨티비는 가능한 방향의 개수가 4가지
		// 2번은 2가지
		// 5번은 1가지. 나머지 내용은 다 똑같음
		if (info == 1 || info == 3 || info == 4) {
			for (int k = 0; k < 4; k++) {
				int[][] temp = copy(map);
				cctvControl(true, info, k, r, c, temp);
				pick(cnt + 1, temp);
			}
	
		} else if (info == 2) {
			for (int k = 0; k < 2; k++) {
				int[][] temp = copy(map);
				cctvControl(true, info, k, r, c, temp);
				pick(cnt + 1, temp);
			}
		} else if (info == 5) {
			int[][] temp = copy(map);
			cctvControl(true, info, 0, r, c, temp);
			pick(cnt + 1, temp);
		}
	}

	// true면 on, false면 off < 이부분은 원래 껐다 켰다 반복하려고 했는데 배열 복사로 해결했기 때문에 필요없어짐
	// 가능한 방향 다 
	private static void cctvControl(boolean flag, int info, int k, int r, int c, int[][] map) {
		if (info == 1) {
			if (k == 0)
				down(flag, r, c, map);
			else if (k == 1)
				up(flag, r, c, map);
			else if (k == 2)
				left(flag, r, c, map);
			else if (k == 3)
				right(flag, r, c, map);
		} else if (info == 2) {
			if (k == 0) {
				left(flag, r, c, map);
				right(flag, r, c, map);
			} else if (k == 1) {
				up(flag, r, c, map);
				down(flag, r, c, map);
			}
		} else if (info == 3) {
			if (k == 0) {
				up(flag, r, c, map);
				right(flag, r, c, map);
			} else if (k == 1) {
				right(flag, r, c, map);
				down(flag, r, c, map);
			} else if (k == 2) {
				down(flag, r, c, map);
				left(flag, r, c, map);
			} else if (k == 3) {
				left(flag, r, c, map);
				up(flag, r, c, map);
			}
		} else if (info == 4) {
			if (k == 0) {
				up(flag, r, c, map);
				right(flag, r, c, map);
				left(flag, r, c, map);
			} else if (k == 1) {
				up(flag, r, c, map);
				right(flag, r, c, map);
				down(flag, r, c, map);
			} else if (k == 2) {
				down(flag, r, c, map);
				left(flag, r, c, map);
				right(flag, r, c, map);
			} else if (k == 3) {
				left(flag, r, c, map);
				up(flag, r, c, map);
				down(flag, r, c, map);
			}
		} else if (info == 5) {
			up(flag, r, c, map);
			right(flag, r, c, map);
			down(flag, r, c, map);
			left(flag, r, c, map);
		}
	}
	
	// 방향만 달라지는 거라 dr dc 배열 만들어서 하면 하나로 합칠 수 있을 듯
	private static void up(boolean flag, int r, int c, int[][] map) {
		int index = 1;
		while (true) {
			int nr = r + -1 * index;

			if (nr < 0 || nr >= N || map[nr][c] == 6)
				break;

			if (flag && map[nr][c] == 0)
				map[nr][c] = -1;
			else if (!flag && map[nr][c] == -1)
				map[nr][c] = 0;

			index++;
		}
	}

	private static void down(boolean flag, int r, int c, int[][] map) {
		int index = 1;
		while (true) {
			int nr = r + 1 * index;

			if (nr < 0 || nr >= N || map[nr][c] == 6)
				break;

			if (flag && map[nr][c] == 0)
				map[nr][c] = -1;
			else if (!flag && map[nr][c] == -1)
				map[nr][c] = 0;
			index++;
		}
	}

	private static void left(boolean flag, int r, int c, int[][] map) {
		int index = 1;
		while (true) {
			int nc = c + -1 * index;

			if (nc < 0 || nc >= M || map[r][nc] == 6)
				break;

			if (flag && map[r][nc] == 0)
				map[r][nc] = -1;
			else if (!flag && map[r][nc] == -1)
				map[r][nc] = 0;

			index++;
		}
	}

	private static void right(boolean flag, int r, int c, int[][] map) {
		int index = 1;
		while (true) {
			int nc = c + 1 * index;

			if (nc < 0 || nc >= M || map[r][nc] == 6)
				break;

			if (flag && map[r][nc] == 0)
				map[r][nc] = -1;
			else if (!flag && map[r][nc] == -1)
				map[r][nc] = 0;

			index++;
		}
	}

	// 씨씨티비 끌때 겹치는 남의 감시 영역도 꺼지는 문제 발견
	// 내가 켰던 것만 끌수 있게 하는 방법 => 켰던 걸 기억해 두기
	private static int[][] copy(int[][] map) {
		int[][] temp = new int[N][M];
		for (int i = 0; i < N; i++) {
			System.arraycopy(map[i], 0, temp[i], 0, map[0].length);
		}
		return temp;
	}
}