[BaekJoon] 15683번 감시 (Java) 문제 풀이 [Gold 3]

문제

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

 

어떻게 풀 것인가?

CCTV 방향 탐색을 위한 순열 생성

• permutation(0, cctvList.size())을 호출하여 DFS 기반 순열 생성을 수행한다.
• 각 CCTV는 최대 4가지 방향을 가질 수 있으므로, 모든 CCTV의 가능한 방향 조합을 만들어서 하나씩 테스트한다.
• 모든 CCTV에 대해 방향이 결정되면, 원본 map을 copyMap에 복사한 후, 해당 조합으로 CCTV 감시를 수행한다.

CCTV 감시 영역 설정

• direction(CCTV cctv, int d) 함수는 CCTV의 종류에 따라 감시 방향을 설정하는 역할을 한다.
• 각 CCTV는 다음과 같이 감시할 방향을 결정한다:
  • 1번: 한 방향 감시
  • 2번: 서로 반대 방향 두 곳 감시
  • 3번: 직각 방향 두 곳 감시
  • 4번: 세 방향 감시
  • 5번: 네 방향 모두 감시
• 결정된 방향에 따라 watch(CCTV cctv, int d)를 호출해 감시 영역을 설정한다.

감시 영역 설정 (BFS)

• watch(CCTV cctv, int d) 함수는 BFS(너비 우선 탐색) 방식으로 CCTV의 감시 영역을 설정한다.
• 특정 방향 d로 이동하면서 벽(6)을 만나기 전까지 감시 영역을 확장한다.
• 감시된 공간을 -1로 표시하여 구분한다.
• 이미 감시된 공간이거나 다른 CCTV가 있는 경우, 계속 탐색을 진행한다.

사각지대 계산 및 최소값 갱신

• getBlindSpot() 함수는 copyMap에서 0(감시되지 않은 영역)의 개수를 세어 사각지대 크기를 구한다.
• 사각지대가 가장 작은 값을 유지하도록 answer 변수를 갱신한다.

 

풀면서 놓쳤던점

생각보다 고려해야할 것들이 너무 많았다..

 

이 문제를 통해 얻어갈 것

• 백트래킹(DFS): CCTV의 모든 방향 조합을 생성하여 탐색.
• BFS: CCTV의 감시 영역을 확장.
• 브루트포스(완전 탐색): 모든 경우를 고려하여 최적해 탐색.
• 맵 복사 및 시뮬레이션: 기존 맵을 유지하면서 다양한 경우의 수를 테스트.

 

 

내 코드 

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

public class Main {

	private static int N, M;
	private static int[][] map;
	private static int[][] copyMap;
	private static int[] output;
	private static ArrayList<CCTV> cctvList;
	private static int[] dx = { -1, 0, 1, 0 }; // 상 우 하 좌 시계방향 순서
	private static int[] dy = { 0, 1, 0, -1 };
	private static int answer = Integer.MAX_VALUE;

	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];
		cctvList = new ArrayList<>();

		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) {
					cctvList.add(new CCTV(map[i][j], i, j));
				}
			}
		}

		output = new int[cctvList.size()]; // 순열을 담을 배열
		permutation(0, cctvList.size());

		System.out.println(answer);
	}

	// DFS로 상하좌우 4방향 중에서 cctv의 총 개수, r만큼을 순서대로 뽑는 순열을 구함
	public static void permutation(int depth, int r) {
		if (depth == r) {

			// Copy original 'map' array
			copyMap = new int[N][M];
			for (int i = 0; i < map.length; i++) {
				System.arraycopy(map[i], 0, copyMap[i], 0, map[i].length);
			}

			// cctv번호와 순열로 뽑혀진 방향에 맞는 상하좌우 방향 설정
			for (int i = 0; i < cctvList.size(); i++) {
				direction(cctvList.get(i), output[i]);
			}

			// 사각 지대 구하기
			findBlindSpot();

			return;
		}

		for (int i = 0; i < 4; i++) {
			output[depth] = i;
			permutation(depth + 1, r);
		}
	}

	// 각 cctv 번호와 순열로 뽑혀진 방향에 맞게 감시
	private static void direction(CCTV cctv, int d) {
		int cctvNum = cctv.num;

		if (cctvNum == 1) {
			if (d == 0)
				spyCCTV(cctv, 0);
			else if (d == 1)
				spyCCTV(cctv, 1);
			else if (d == 2)
				spyCCTV(cctv, 2);
			else if (d == 3)
				spyCCTV(cctv, 3);
		} else if (cctvNum == 2) {
			if (d == 0 || d == 2) {
				spyCCTV(cctv, 0);
				spyCCTV(cctv, 2);
			} else {
				spyCCTV(cctv, 1);
				spyCCTV(cctv, 3);
			}
		} else if (cctvNum == 3) {
			if (d == 0) {
				spyCCTV(cctv, 0);
				spyCCTV(cctv, 1);
			} else if (d == 1) {
				spyCCTV(cctv, 1);
				spyCCTV(cctv, 2);
			} else if (d == 2) {
				spyCCTV(cctv, 2);
				spyCCTV(cctv, 3);
			} else if (d == 3) {
				spyCCTV(cctv, 0);
				spyCCTV(cctv, 3);
			}
		} else if (cctvNum == 4) {
			if (d == 0) {
				spyCCTV(cctv, 0);
				spyCCTV(cctv, 1);
				spyCCTV(cctv, 3);
			} else if (d == 1) {
				spyCCTV(cctv, 0);
				spyCCTV(cctv, 1);
				spyCCTV(cctv, 2);
			} else if (d == 2) {
				spyCCTV(cctv, 1);
				spyCCTV(cctv, 2);
				spyCCTV(cctv, 3);
			} else if (d == 3) {
				spyCCTV(cctv, 0);
				spyCCTV(cctv, 2);
				spyCCTV(cctv, 3);
			}
		} else if (cctvNum == 5) {
			spyCCTV(cctv, 0);
			spyCCTV(cctv, 1);
			spyCCTV(cctv, 2);
			spyCCTV(cctv, 3);
		}
	}

	// BFS로 방향에 맞게 감시
	private static void spyCCTV(CCTV cctv, int d) {
		Queue<CCTV> queue = new LinkedList<>();
		boolean[][] visited = new boolean[N][M];

		queue.add(cctv);
		visited[cctv.x][cctv.y] = true;

		while (!queue.isEmpty()) {
			int nx = queue.peek().x + dx[d];
			int ny = queue.poll().y + dy[d];

			// 범위를 벗어나거나 벽을 만나면 끝
			if (!range(nx, ny) || copyMap[nx][ny] == 6) {
				break;
			}

			if (copyMap[nx][ny] == 0) {
				copyMap[nx][ny] = -1; // 빈칸이라면 감시할 수 있다는 의미로 -1
				queue.add(new CCTV(cctv.num, nx, ny));
			} else { // 다른 cctv가 있거나 이미 감시된 칸이라면 그냥 통과
				queue.add(new CCTV(cctv.num, nx, ny));
			}
		}
	}

	private static boolean range(int x, int y) {
		return 0 <= x && x < N && 0 <= y && y < M;
	}

	// 사각 지대 구하기
	private static void findBlindSpot() {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (copyMap[i][j] == 0) {
					cnt++;
				}
			}
		}
		answer = Math.min(answer, cnt);
	}

}

class CCTV {
	int num;
	int x;
	int y;

	CCTV(int num, int x, int y) {
		this.num = num;
		this.x = x;
		this.y = y;
	}
}

 

참고

x