[Baekjoon] 백준 15683 감시 (G4^ / DFS) - Java

링크

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

15683번: 감시

 

 

 

 

문제 해석

- 문제 분석

CCTV는 총 5가지가 존재함
1번 : 1방향
2번 : 대칭적인 2방향
3번 : 수직인 2방향
4번 : 3방향
5번 : 4방향

CCTV는 90도 각도로 회전이 가능함
CCTV는 벽을 뚫을 수 없음
CCTV가 CCTV를 뚫고 감시는 가능
CCTV로 볼 수 없는 사각지대가 최소가 되도록 CCTV를 회전시키기

 

 

- 입력
첫 번째 줄 : N M  # N=세로, M=가로
나머지 줄 : 지도 정보


- 출력 : 최소로 나올 수 있는 사각지대 개수

 

 

 

 

풀이 & 코드 해석

0 : 사각지대
1~5 : 감시카메라
6 : 벽
9 : 감시 가능한 위치

 

해당 문제는 감시 카메라가 여러 대일 때 각 카메라를 최적으로 회전해 주는 하는 것이 가장 중요합니다.

 

따라서 DFS를 통하여 각 카메라를 회전하는 모든 경우의 수를 구하였습니다.

 

모든 경우의 수를 구할 때마다 정해진 회전 방향으로 CCTV가 탐색하도록 하였으며, 이때 한쪽 방향으로 끝까지 탐색하도록 하였습니다.

 

최종적으로는 사각지대를 세서 최소값을 찾도록 하였습니다.

 

 

- 구현 순서
모두 회전 방향을 정하자 (dfs)
정해진 회전방향으로 cctv가 탐색하자
사각지대를 세자

 

 

 

 

코드

package day10;

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

public class 감시 {

	static int[][] map;
	static int[][] copyMap;
	static int N, M, answer;
	static LinkedList<Point> q;

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

		// 첫 번째 줄
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		answer = Integer.MAX_VALUE;

		map = new int[N][M];
		q = new LinkedList<>();

		// 나머지 줄
		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] != 0 && map[i][j] != 6) {
					q.offer(new Point(i, j, map[i][j], 0));
				}
			}
		}

//		print(map);

		sel = new int[q.size()];
		if (q.size() != 0) {
			dfs(0);
		} else {
			int nowAnswer = 0;
			for (int x = 0; x < map.length; x++) {
				for (int y = 0; y < map[0].length; y++) {
					if (map[x][y] == 0) {
						nowAnswer++;
					}
				}
			}
			answer = Math.min(nowAnswer, answer);
		}

		System.out.println(answer);

	} // [E] main

	static int[] sel;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	private static void dfs(int cnt) {
		// basis
		if (cnt == q.size()) {
			copyMap = new int[N][M];
			mapCopy(map, copyMap);

			// 2) 각 cctv를 정해진 회전방향으로 탐색
			// cctv 개수만큼 반복
			for (int i = 0; i < q.size(); i++) {
				Point p = q.get(i);

				// cctv의 종류에 따라서 다른 결과 도출
				if (p.camera == 1) {
					for (int c = 0; c < 1; c++) {
						search(p, c, i);
					}
				} else if (p.camera == 2) {
					for (int c = 0; c < 3; c = c + 2) {
						search(p, c, i);
					}
				} else if (p.camera == 3) {
					for (int c = 0; c < 2; c = c + 1) {
						search(p, c, i);
					}
				} else if (p.camera == 4) {
					for (int c = 0; c < 3; c = c + 1) {
						search(p, c, i);
					}
				} else if (p.camera == 5) {
					for (int c = 0; c < 4; c++) {
						search(p, c, i);
					}
				}

				// 3) 사각지대 개수 count
				int nowAnswer = 0;
				for (int x = 0; x < copyMap.length; x++) {
					for (int y = 0; y < copyMap[0].length; y++) {
						if (copyMap[x][y] == 0) {
							nowAnswer++;
						}
					}
				}
				answer = Math.min(nowAnswer, answer);
			}
			return;
		}

		// inductive
		// 1) 회전 방향을 정함
		for (int i = 0; i < 4; i++) {
			sel[cnt] = i;
			dfs(cnt + 1);
		}

	}

	private static void mapCopy(int[][] map, int[][] copyMap) {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				copyMap[i][j] = map[i][j];
			}
		}
	}

	private static void search(Point p, int c, int i) {
		// 한쪽 끝으로 반복
		for (int d = 1;; d++) {
			// 회전 방향 + 카메라의 감시 방향을 향해서 끝까지 보기
			int nx = p.x + dx[(sel[i] + c) % 4] * d;
			int ny = p.y + dy[(sel[i] + c) % 4] * d;
			// 지도 내에 위치하고 / 벽이 아니라면
			if (nx >= 0 && nx < copyMap.length && ny >= 0 && ny < copyMap[0].length && copyMap[nx][ny] != 6) {
				if (copyMap[nx][ny] == 0) {
					copyMap[nx][ny] = 9;
				}
			} else {
				break;
			}
		}

	}

	static class Point {
		int x;
		int y;
		int camera;
		int rot;

		Point(int x, int y, int camera, int rot) {
			this.x = x;
			this.y = y;
			this.camera = camera;
			this.rot = rot;
		}

	}

	private static void print(int[][] map) {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}
}

 

 

 

 

발생한 문제 & 해결 방안

테스트 케이스 38%에서 틀리는 현상이 발생하였는데, 생각해보니 카메라가 하나도 없는 경우를 따로 지정하지 않아서 발생한 문제였다.

 

아무 것도 없을 때와 같은 부분도 잘 체크하자!

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java