[백준] 감시 15683

Coding Test/백준

[백준] 감시 15683 - 자바

lsh2613 2023. 12. 12. 22:33

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

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감

www.acmicpc.net

문제 풀이

이 문제의 입력조건을 보면 값이 작은 편이라 완전탐색을 할 수 있고 완전탐색을 하기 위해서 백트래킹을 사용할 수 있다.

먼저 본인의 접근법은 각 cctv가 감시할 수 있는 모든 경우의 수를 조합하여 백트래킹을 실행하여 cctv가 켜지면 감시당하는 지역의 값을 -1, cctv가 꺼지면 (백트래킹이기 때문에 cctv를 꺼야 된다) 해당 지역의 값을 +1을 해준다.

모든 cctv를 탐색이 완료됐다면 최솟값을 업데이트 해준다.

재귀함수를 사용하고 구현에 있어 실수를 방지하기 위해 전역변수와 상수를 적극 활용하자.

static int N, M;
static int[][] board;
static List<int[]> cctvs = new ArrayList<>();
static final int wall = 6;
static int result = Integer.MAX_VALUE;
static final int ON = -1;
static final int OFF = 1;

init

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
board = new int[N][M];
for (int i = 0; i < N; i++) {
    st = new StringTokenizer(br.readLine());
    for (int j = 0; j < M; j++) {
        board[i][j] = Integer.parseInt(st.nextToken());
        if (1 <= board[i][j] && board[i][j] <= 5) {
            cctvs.add(new int[]{i, j});
        }
    }
}

fullSearch를 통한 백트래킹 실행

fullSearch(1);

System.out.println(result);

now값이 cctv의 개수보다 커지면 모든 cctv를 탐색했다는 뜻으로 최솟값을 업데이트 해준 후 해당 재귀를 종료한다.

해당 cctv 번호에 따라 탐색 방향이 바뀌기 때문에 해당 번호에 대한 모든 경우의 수를 탐색하고

해당 방향으로 cctvOn-> 재귀 -> cctvOff를 반복해준다.

이때 방향은 cctvOn/Off의 두 번째 매개변수인 정수형 값을 통해 상:0 우:1 하:2 좌:3으로 설정

static void fullSearch(int now) {
    if (now > cctvs.size()) {
        int blindSpots = 0;
        for (int[] line : board) {
            int zeros = (int) Arrays.stream(line).filter(i -> i == 0).count();
            blindSpots += zeros;
        }
        result = Math.min(result, blindSpots);
        return;
    }

    int[] cctv = cctvs.get(now);
    switch (board[cctv[0]][cctv[1]]) {
        case 1:
            for (int i = 0; i < 4; i++) { // 상 우 하 좌
                cctvSwitch(cctv, i, ON);
                fullSearch(now + 1);
                cctvSwitch(cctv, i, OFF);
            }
            break;
        case 2:
            for (int i = 0; i < 2; i++) { // 상하 우좌
                cctvSwitch(cctv, i, ON);
                cctvSwitch(cctv, i + 2, ON);
                fullSearch(now + 1);
                cctvSwitch(cctv, i, OFF);
                cctvSwitch(cctv, i + 2, OFF);
            }
            break;
        case 3:
            for (int i = 0; i < 4; i++) { // 상우 우하 하좌 좌상
                cctvSwitch(cctv, i, ON);
                cctvSwitch(cctv, (i + 1) % 4, ON);
                fullSearch(now + 1);
                cctvSwitch(cctv, i, OFF);
                cctvSwitch(cctv, (i + 1) % 4, OFF);
            }
            break;
        case 4:
            for (int i = 0; i < 4; i++) { // 상우하 우하좌 하좌상 좌상우
                cctvSwitch(cctv, i, ON);
                cctvSwitch(cctv, (i + 1) % 4, ON);
                cctvSwitch(cctv, (i + 2) % 4, ON);
                fullSearch(now + 1);
                cctvSwitch(cctv, i, OFF);
                cctvSwitch(cctv, (i + 1) % 4, OFF);
                cctvSwitch(cctv, (i + 2) % 4, OFF);
            }
            break;
        case 5:
            for (int i = 0; i < 4; i++) {
                cctvSwitch(cctv, i, ON);
            }
            fullSearch(now + 1);
            for (int i = 0; i < 4; i++) {
                cctvSwitch(cctv, i, OFF);
            }
    }
}

위에서 언급한 방향에 맞게 dx dy도 맞춰주고 cctv를 키면(ON) 해당 지역을 -1, 끄면(OFF) 해당 지역을 +1을 해주기로 했고 해당 값은 상수로 설정해주었고 switchFlag를 통해 받고 있음에 유의

// dir 값에 따라 상:0 우:1 하:2 좌:3
// 그 값에 해당하는 dx dy 선언
public static int[] dx = {-1, 0, 1, 0};
public static int[] dy = {0, 1, 0, -1};

// cctv가 켜지면 0 이하인 곳만 -1씩 감소 (1보다 큰 곳은 cctv OR 벽이기 때문에)
// cctv가 꺼지면 +1
static void cctvSwitch(int[] cctv, int dir, int switchFlag) {
    Queue<int[]> q = new LinkedList<>();
    q.offer(new int[]{cctv[0], cctv[1]});
    while (!q.isEmpty()) {
        int[] now = q.poll();
        int nx = now[0] + dx[dir];
        int ny = now[1] + dy[dir];

        if (nx < 0 || nx >= N || ny < 0 || ny >= M || board[nx][ny] == wall) {
            break;
        }

        if (board[nx][ny] <= 0) {
            board[nx][ny] += switchFlag;
        }
        q.offer(new int[]{nx, ny});
    }
}

코드

package 백준;

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

public class Main {
    static int N, M;
    static int[][] board;
    static List<int[]> cctvs = new ArrayList<>();
    static final int wall = 6;
    static int result = Integer.MAX_VALUE;
    static final int ON = -1;
    static final int OFF = 1;

    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());
        board = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if (1 <= board[i][j] && board[i][j] <= 5) {
                    cctvs.add(new int[]{i, j});
                }
            }
        }
        fullSearch(1);

        System.out.println(result);
    }

    static void fullSearch(int now) {
        if (now > cctvs.size()) {
            int blindSpots = 0;
            for (int[] line : board) {
                int zeros = (int) Arrays.stream(line).filter(i -> i == 0).count();
                blindSpots += zeros;
            }
            result = Math.min(result, blindSpots);
            return;
        }

        int[] cctv = cctvs.get(now);
        switch (board[cctv[0]][cctv[1]]) {
            case 1:
                for (int i = 0; i < 4; i++) { // 상 우 하 좌
                    cctvSwitch(cctv, i, ON);
                    fullSearch(now + 1);
                    cctvSwitch(cctv, i, OFF);
                }
                break;
            case 2:
                for (int i = 0; i < 2; i++) { // 상하 우좌
                    cctvSwitch(cctv, i, ON);
                    cctvSwitch(cctv, i + 2, ON);
                    fullSearch(now + 1);
                    cctvSwitch(cctv, i, OFF);
                    cctvSwitch(cctv, i + 2, OFF);
                }
                break;
            case 3:
                for (int i = 0; i < 4; i++) { // 상우 우하 하좌 좌상
                    cctvSwitch(cctv, i, ON);
                    cctvSwitch(cctv, (i + 1) % 4, ON);
                    fullSearch(now + 1);
                    cctvSwitch(cctv, i, OFF);
                    cctvSwitch(cctv, (i + 1) % 4, OFF);
                }
                break;
            case 4:
                for (int i = 0; i < 4; i++) { // 상우하 우하좌 하좌상 좌상우
                    cctvSwitch(cctv, i, ON);
                    cctvSwitch(cctv, (i + 1) % 4, ON);
                    cctvSwitch(cctv, (i + 2) % 4, ON);
                    fullSearch(now + 1);
                    cctvSwitch(cctv, i, OFF);
                    cctvSwitch(cctv, (i + 1) % 4, OFF);
                    cctvSwitch(cctv, (i + 2) % 4, OFF);
                }
                break;
            case 5:
                for (int i = 0; i < 4; i++) {
                    cctvSwitch(cctv, i, ON);
                }
                fullSearch(now + 1);
                for (int i = 0; i < 4; i++) {
                    cctvSwitch(cctv, i, OFF);
                }
        }
    }

    // dir 값에 따라 상:0 우:1 하:2 좌:3
    // 그 값에 해당하는 dx dy 선언
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, 1, 0, -1};

    // cctv가 켜지면 0 이하인 곳만 -1씩 감소 (1보다 큰 곳은 cctv OR 벽이기 때문에)
    // cctv가 꺼지면 +1
    static void cctvSwitch(int[] cctv, int dir, int switchFlag) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{cctv[0], cctv[1]});
        while (!q.isEmpty()) {
            int[] now = q.poll();
            int nx = now[0] + dx[dir];
            int ny = now[1] + dy[dir];

            if (nx < 0 || nx >= N || ny < 0 || ny >= M || board[nx][ny] == wall) {
                break;
            }

            if (board[nx][ny] <= 0) {
                board[nx][ny] += switchFlag;
            }
            q.offer(new int[]{nx, ny});
        }
    }

}