close
프로필 배경
프로필 로고

JinHxxxxKim

알고리즘 · 2024. 2. 21. fullscreen 넓게보기

[BOJ] - 감시 / 15686번 (Java)

[BOJ] - 감시 / 15686번 (Java)

[BOJ] - 감시 / 15686번 (Java)

1. 문제 접근

사무실의 상태가 주어지고, 주어진 CCTV의 방향을 결정해서 나올 수 있는 사무실 사각지대 개수의 최소값을 구하는 문제다.

 

 

1번부터 5번까지의 CCTV가 존재하며, 각 CCTV가 회전하여 감시할 수 있는 방향은 다음과 같다.

  1. 번 CCTV: {상}, {하}, {좌}, {우} 4가지
  2. 번 CCTV: {좌, 우}, {상, 하} 2가지
  3. 번 CCTV: {상, 우}, {우, 하}, {하, 좌}, {좌, 상} 4가지
  4. 번 CCTV: {좌, 상, 우}, {상, 우, 하}, {우, 하, 좌}, {하, 좌, 상} 4가지
  5. 번 CCTV: {상, 하, 좌, 우} 1가지

총 CCTV의 개수는 8개를 넘지 않으므로, 가능한 모든 경우의 수를 따져봐도 4^8을 넘지 않는다.

 

따라서 모든 CCTV에 대해 가능한 모든 회전을 돌려본 뒤, 사각지대를 계산하였다.

 

각 CCTV의 경우에 따라 각각의 방향을 상수로 정의하였다.

  1. 번 CCTV: {상}, {하}, {좌}, {우} = 0, 1, 2, 3
  2. 번 CCTV: {좌, 우}, {상, 하} = 0, 1
  3. 번 CCTV: {상, 우}, {우, 하}, {하, 좌}, {좌, 상} = 0, 1, 2, 3
  4. 번 CCTV: {좌, 상, 우}, {상, 우, 하}, {우, 하, 좌}, {하, 좌, 상} = 0, 1, 2, 3
  5. 번 CCTV: {상, 하, 좌, 우} = -1

하나의 CCTV가 하나의 방향만 바라보는 것이 아닌 한번에 여러방향을 바라볼 수 있으므로 별도의 상수로 치환하여 저장하였다.

 

// 현재 살펴볼 CCTV
CCTV currCCTV = cctvs.get(currCCTVIdx);
switch (currCCTV.type) {
case CCTV_1:
    // dir: {0: 상, 1: 우, 2: 하, 3: 좌}
    for (int dir = 0; dir < 4; ++dir) {
        cctvDirection[currCCTVIdx] = dir;
        combination(currCCTVIdx + 1);
    }
    break;
case CCTV_2:
    // dir: {0: 수평, 1: 수직}
    for (int dir = 0; dir < 2; ++dir) {
        cctvDirection[currCCTVIdx] = dir;
        combination(currCCTVIdx + 1);
    }
    break;
case CCTV_3:
    // dir: {0: 상우, 1: 우하, 2: 하좌, 3: 좌상}
    for (int dir = 0; dir < 4; ++dir) {
        cctvDirection[currCCTVIdx] = dir;
        combination(currCCTVIdx + 1);
    }
    break;
case CCTV_4:
    // dir: {0: 좌상우, 1: 상우하, 2: 우하좌, 3: 하좌상}
    for (int dir = 0; dir < 4; ++dir) {
        cctvDirection[currCCTVIdx] = dir;
        combination(currCCTVIdx + 1);
    }
    break;
case CCTV_5:
    // dir: {-1: 상하좌우}
    cctvDirection[currCCTVIdx] = -1;
    combination(currCCTVIdx + 1);
    break;
}

 

모든 CCTV의 방향을 정했다면 이는 기저조건에 해당하고 사각지대의 개수를 계산하였다.

 

여러 경우를 확인해봐야하므로 원본 배열은 변경하지 않고, 임시배열에 복사하여 변경 후, 사각지대를 카운팅했다.

 

// 기저조건
if (currCCTVIdx == cctvs.size()) {
    // 원본 배열 유지를 위한 배열 복사
    tempMap = new int[N][M];
    for (int row = 0; row < N; ++row) {
        for (int col = 0; col < M; ++col) {
            tempMap[row][col] = map[row][col];
        }
    }

    // 현재 선택한 CCTV의 방향에 대해 사각지대의 크기를 구한다
    // 모든 CCTV에 대해 방향을 정해두었으므로, 정한 방향으로 map을 변형해가며 카운팅
    for (int cctvIdx = 0; cctvIdx < cctvs.size(); ++cctvIdx) {
        CCTV currCCTV = cctvs.get(cctvIdx);
        int direction = cctvDirection[cctvIdx];
        ...
    }
    ...
}

 

CCTV가 감시 할 수 있는 영역에 대해서는 모두 한 방향으로 뻗어 나간다.

 

따라서 CCTV의 위치와 방향을 매개변수로 갖는 메소드를 만들어 재사용했다.

 

CCTV가 감시할 수 있는 위치는 -1로 변경하여 이후 사각지대 카운팅할 때 -1인 영역은 제외했다.

 

// dir 방향으로 [row, col]부터 사각지대를 없애는 함수
public static void oneWayCCTV(int row, int col, int dir) {
    // 벽을 만나거나, 범위 밖으로 나가기 전까지
    int tempRow = row + dx[dir];
    int tempCol = col + dy[dir];

    while (true) {
        // 범위 체크
        if (tempRow < 0 || tempCol < 0 || tempRow >= N || tempCol >= M)
            break;
        // 벽 체크
        if (tempMap[tempRow][tempCol] == 6)
            break;
        // -1: CCTV의 감시 구역
        tempMap[tempRow][tempCol] = -1;

        tempRow = tempRow + dx[dir];
        tempCol = tempCol + dy[dir];
    }
}

 

4번 CCTV의 경우를 하나의 예시로 설명하겠다.

 

 

4번 CCTV가 감시할 수 있는 경우의 수는 4가지다 

  1. `direction` =  0: 좌+상+우
  2. `direction` =  1: 상+우+하
  3. `direction` =  2: 우+하+좌
  4. `direction` =  3: 하+좌+상

따라서 각 경우에 대해 `oneWayCCTV()`메소드를 호출하여 CCTV가 감시할 수 있는 영역에 대해 표시해둔다.

case CCTV_4:
    // dir: {0: 좌상우, 1: 상우하, 2: 우하좌, 3: 하좌상}
    switch (direction) {
    case 0:
        oneWayCCTV(currCCTV.x, currCCTV.y, LEFT);
        oneWayCCTV(currCCTV.x, currCCTV.y, UP);
        oneWayCCTV(currCCTV.x, currCCTV.y, RIGHT);
        break;
    case 1:
        oneWayCCTV(currCCTV.x, currCCTV.y, UP);
        oneWayCCTV(currCCTV.x, currCCTV.y, RIGHT);
        oneWayCCTV(currCCTV.x, currCCTV.y, DOWN);
        break;
    case 2:
        oneWayCCTV(currCCTV.x, currCCTV.y, RIGHT);
        oneWayCCTV(currCCTV.x, currCCTV.y, DOWN);
        oneWayCCTV(currCCTV.x, currCCTV.y, LEFT);
        break;
    case 3:
        oneWayCCTV(currCCTV.x, currCCTV.y, DOWN);
        oneWayCCTV(currCCTV.x, currCCTV.y, LEFT);
        oneWayCCTV(currCCTV.x, currCCTV.y, UP);
        break;
    }
    break;

 

2. 코드

package boj;

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

/**
 * [BOJ] - 감시 / 15686번 
 * @author JinHxxxxKim
 * 
 * 1. 사무실의 세로 크기 N과 가로 크기 M을 입력받는다.
 * 2. 사무실 각 칸의 정보를 입력받는다.
 * 3. 각 CCTV마다 설정할 수 있는 모든 경우의 수를 구한 뒤, 사각지대를 구한다.
 * 		- CCTV1: 총 4가지 경우의 수 
 * 		- CCTV2: 종 2가지 경우의 수
 * 		- CCTV3: 총 4가지 경우의 수
 * 		- CCTV4: 총 4가지 경우의 수
 * 		- CCTV5: 총 1가지 경우의 수
 * 		CCTV의 개수는 최대 8개를 넘지않는다. -> 4^8 = 65536
 * 
 * 모든  CCTV는 CCTV1번의 반복이다.
 */
public class Sol_15683 {
	// 12시, 3시, 6시, 9시 순서 [0, 1, 2, 3]
	private static final int[] dx = new int[] { -1, 0, 1, 0 };
	private static final int[] dy = new int[] { 0, 1, 0, -1 };

	private static final int CCTV_1 = 1;
	private static final int CCTV_2 = 2;
	private static final int CCTV_3 = 3;
	private static final int CCTV_4 = 4;
	private static final int CCTV_5 = 5;

	private static final int UP = 0;
	private static final int RIGHT = 1;
	private static final int DOWN = 2;
	private static final int LEFT = 3;

	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringBuilder sb = new StringBuilder();
	private static StringTokenizer st;

	private static int N, M;
	private static int[][] map;
	private static int[][] tempMap;
	private static List<CCTV> cctvs; // cctv 정보 저장 리스트
	private static int[] cctvDirection;

	private static int minArea;

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine().trim());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		cctvs = new ArrayList<CCTV>();
		map = new int[N][M];
		for (int row = 0; row < N; ++row) {
			st = new StringTokenizer(br.readLine().trim());
			for (int col = 0; col < M; ++col) {
				map[row][col] = Integer.parseInt(st.nextToken());
				if (map[row][col] != 0 && map[row][col] != 6) {
					cctvs.add(new CCTV(row, col, map[row][col]));
				}
			}
		}

		// cctv의 방향 저장
		cctvDirection = new int[cctvs.size()];
		minArea = M * N;
		combination(0);

		System.out.println(minArea);
	}

	private static void combination(int currCCTVIdx) {
		// 기저조건
		if (currCCTVIdx == cctvs.size()) {
			// 원본 배열 유지를 위한 배열 복사
			tempMap = new int[N][M];
			for (int row = 0; row < N; ++row) {
				for (int col = 0; col < M; ++col) {
					tempMap[row][col] = map[row][col];
				}
			}
			
			// 현재 선택한 CCTV의 방향에 대해 사각지대의 크기를 구한다
			// 모든 CCTV에 대해 방향을 정해두었으므로, 정한 방향으로 map을 변형해가며 카운팅
			for (int cctvIdx = 0; cctvIdx < cctvs.size(); ++cctvIdx) {
				CCTV currCCTV = cctvs.get(cctvIdx);
				int direction = cctvDirection[cctvIdx];
				switch (currCCTV.type) {
				case CCTV_1:
					// dir: {0: 상, 1: 우, 2: 하, 3: 좌}
					oneWayCCTV(currCCTV.x, currCCTV.y, direction);
					break;
				case CCTV_2:
					// dir: {0: 수평, 1: 수직}
					switch (direction) {
					case 0:
						oneWayCCTV(currCCTV.x, currCCTV.y, RIGHT);
						oneWayCCTV(currCCTV.x, currCCTV.y, LEFT);
						break;
					case 1:
						oneWayCCTV(currCCTV.x, currCCTV.y, UP);
						oneWayCCTV(currCCTV.x, currCCTV.y, DOWN);
						break;
					}
					break;
				case CCTV_3:
					// dir: {0: 상우, 1: 우하, 2: 하좌, 3: 좌상}
					switch (direction) {
					case 0:
						oneWayCCTV(currCCTV.x, currCCTV.y, UP);
						oneWayCCTV(currCCTV.x, currCCTV.y, RIGHT);
						break;
					case 1:
						oneWayCCTV(currCCTV.x, currCCTV.y, RIGHT);
						oneWayCCTV(currCCTV.x, currCCTV.y, DOWN);
						break;
					case 2:
						oneWayCCTV(currCCTV.x, currCCTV.y, DOWN);
						oneWayCCTV(currCCTV.x, currCCTV.y, LEFT);
						break;
					case 3:
						oneWayCCTV(currCCTV.x, currCCTV.y, LEFT);
						oneWayCCTV(currCCTV.x, currCCTV.y, UP);
						break;
					}
					break;
				case CCTV_4:
					// dir: {0: 좌상우, 1: 상우하, 2: 우하좌, 3: 하좌상}
					switch (direction) {
					case 0:
						oneWayCCTV(currCCTV.x, currCCTV.y, LEFT);
						oneWayCCTV(currCCTV.x, currCCTV.y, UP);
						oneWayCCTV(currCCTV.x, currCCTV.y, RIGHT);
						break;
					case 1:
						oneWayCCTV(currCCTV.x, currCCTV.y, UP);
						oneWayCCTV(currCCTV.x, currCCTV.y, RIGHT);
						oneWayCCTV(currCCTV.x, currCCTV.y, DOWN);
						break;
					case 2:
						oneWayCCTV(currCCTV.x, currCCTV.y, RIGHT);
						oneWayCCTV(currCCTV.x, currCCTV.y, DOWN);
						oneWayCCTV(currCCTV.x, currCCTV.y, LEFT);
						break;
					case 3:
						oneWayCCTV(currCCTV.x, currCCTV.y, DOWN);
						oneWayCCTV(currCCTV.x, currCCTV.y, LEFT);
						oneWayCCTV(currCCTV.x, currCCTV.y, UP);
						break;
					}
					break;
				case CCTV_5:
					// dir: {-1: 상하좌우}
					oneWayCCTV(currCCTV.x, currCCTV.y, UP);
					oneWayCCTV(currCCTV.x, currCCTV.y, RIGHT);
					oneWayCCTV(currCCTV.x, currCCTV.y, DOWN);
					oneWayCCTV(currCCTV.x, currCCTV.y, LEFT);
					break;
				}
			}
			// 사각지대 계산
			int result = getZeroArea();
			// 사각지대 최소 개수 갱신
			minArea = Math.min(minArea, result);
			return;
		}
		
		// 현재 살표볼 CCTV
		CCTV currCCTV = cctvs.get(currCCTVIdx);
		switch (currCCTV.type) {
		case CCTV_1:
			// dir: {0: 상, 1: 우, 2: 하, 3: 좌}
			for (int dir = 0; dir < 4; ++dir) {
				cctvDirection[currCCTVIdx] = dir;
				combination(currCCTVIdx + 1);
			}
			break;
		case CCTV_2:
			// dir: {0: 수평, 1: 수직}
			for (int dir = 0; dir < 2; ++dir) {
				cctvDirection[currCCTVIdx] = dir;
				combination(currCCTVIdx + 1);
			}
			break;
		case CCTV_3:
			// dir: {0: 상우, 1: 우하, 2: 하좌, 3: 좌상}
			for (int dir = 0; dir < 4; ++dir) {
				cctvDirection[currCCTVIdx] = dir;
				combination(currCCTVIdx + 1);
			}
			break;
		case CCTV_4:
			// dir: {0: 좌상우, 1: 상우하, 2: 우하좌, 3: 하좌상}
			for (int dir = 0; dir < 4; ++dir) {
				cctvDirection[currCCTVIdx] = dir;
				combination(currCCTVIdx + 1);
			}
			break;
		case CCTV_5:
			// dir: {-1: 상하좌우}
			cctvDirection[currCCTVIdx] = -1;
			combination(currCCTVIdx + 1);
			break;
		}
	}

	// dir 방향으로 [row, col]부터 사각지대를 없애는 함수
	public static void oneWayCCTV(int row, int col, int dir) {
		// 벽을 만나거나, 범위 밖으로 나가기 전까지
		int tempRow = row + dx[dir];
		int tempCol = col + dy[dir];

		while (true) {
			// 범위 체크
			if (tempRow < 0 || tempCol < 0 || tempRow >= N || tempCol >= M)
				break;
			// 벽 체크
			if (tempMap[tempRow][tempCol] == 6)
				break;
			// -1: CCTV의 감시 구역
			tempMap[tempRow][tempCol] = -1;

			tempRow = tempRow + dx[dir];
			tempCol = tempCol + dy[dir];
		}
	}

	// 사각지대 구하는 메소드
	public static int getZeroArea() {
		int sum = 0;
		for (int row = 0; row < N; ++row) {
			for (int col = 0; col < M; ++col) {
				if (tempMap[row][col] == 0) {
					++sum;
				}
			}
		}
		return sum;
	}

	// CCTV 클래스
	static class CCTV {
		int x, y;
		int type;

		public CCTV(int x, int y, int type) {
			super();
			this.x = x;
			this.y = y;
			this.type = type;
		}
	}
}

 

3. 디버깅

CCTV의 종류가 다양하고 각 CCTV가 한 번에 감시할 수 있는 방향도 다양하여 방향 설정을 확실하게 하는데 많은 시간을 사용한 것 같다.

 

2번, 3번, 4번, 5번 CCTV와 같이 한번에 2개 이상의 방향을 감시할 수 있는 CCTV에 대해 방향을 명확하게 설정하는 것이 어려웠던 것 같다.(`direction` =  0: 좌+상+우 etc.)

 

4. 결과

 

'알고리즘' 카테고리의 다른 글

[SWEA] - 최소 스패닝 트리 / 3124번 (Java)  (0) 2024.02.22
[BOJ] - 암호 만들기 / 1759번 (Java)  (0) 2024.02.21
[BOJ] - ABCDE / 13023번 (Java)  (0) 2024.02.21
[SWEA] - 서로소 집합 / 3289번 (Java)  (0) 2024.02.21
[BOJ] - 회전 초밥 / 15961 (Java)  (0) 2024.02.20
알고리즘 관련 글
더 보기

티스토리툴바