[BOJ] 백준 15683번: 감시 (JAVA)

- 문제 출처 : https://www.acmicpc.net/problem/15683

---

1. 생각

정형화되어있는 다익스트라 알고리즘만 잔뜩 풀다가,

창의력이 필요한 구현(시뮬레이션) 문제를 좀 풀어보려고 '감시' 문제를 정했다.

 

총 5가지의 방향이 주어져있는 CCTV를 K개 가지고 있는 사무실에서,

CCTV로 볼 수 없는 사각지대의 최소크기를 반환하는 문제이다.

 

직관적으로 생각했을 때 boolean 2차원 배열을 하나 더 만들고,

감시 가능한 구역을 반복문으로 방향별로 true로 바꿔주고, backtracking 후, 원상복귀 시켜두는 맥락을 생각했다.

 

하지만 생각보다 너무 복잡해서 짜는 데에 어려움이 있었다.

2. 난관 & 해결방법

static class CCTV {
    int x;
    int y;
    int mode;

    public CCTV(int x, int y, int mode) {
        super();

        this.x = x;
        this.y = y;
        this.mode = mode;
    }
}

 

CCTV 들을 관리하기 위해 class를 하나 정의해주었다.

x, y 좌표와 어떤 종류의 CCTV인지 확인하는 mode를 가지도록 만들었다.

 

static int N;
static int M;
static int size;
static int min = 2147483647;
static int[][] map;
static boolean[][] sight;
static final int[] dx = {0, -1, 0, 1};
static final int[] dy = {1, 0, -1, 0};
static List <CCTV> cctvList;

 

그리고 선언한 static 변수, 배열들이다.

N : 사무실의 세로 크기

M : 사무실의 가로 크기

size : CCTV의 개수 (backtracking의 최대 depth)

min : 결과값을 담을 최소값 변수

map[ ][ ] : 초기 사무실의 입력 데이터

sight[ ][ ] : CCTV로 감시 가능한지 아닌지 담는 배열 (true : 감시 가능, false : 사각지대)

dx, dy : 0도, 90도, 180도, 270도 순으로 회전하는 방향 벡터 배열

cctvList : CCTV class들을 담을 List

 

static void backTracking(int depth)

if (depth == size)
{
    int res = 0;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (!sight[i][j] && map[i][j] == 0)
                res ++;
        }
    }

    if (res < min)
        min = res;

    return;
}

 

우선 backTracking 함수에서, depth 에 따라 종료 조건부터 작성했다.

size는 main문에서 CCTV 개수로 설정을 해두었고, 모든 CCTV를 탐색했을 때 결과를 반환하고 종료하는 코드이다.

 

map 2차원 배열 해당 좌표가 0 (빈공간) 이면서, sight 2차원 배열이 false이면,

이 부분은 '사각지대' 로, CCTV가 감시하지 못하는 구역이다.

 

해당 부분의 개수를 세어 min 보다 작으면 저장하도록 설정해두었다. 

 

처음에는 sight만 false일 때로 설정해서, 벽도 사각지대로 세어버려 원하는 값이 나오지 못했는데,

빈공간에 해당하는 map[][] == 0 부분에 한정해서 값을 세면 정확한 값이 나왔다.

 

CCTV nowCCTV = cctvList.get(depth);
int x = nowCCTV.x;
int y = nowCCTV.y;
int mode = nowCCTV.mode;

for (int dir = 0; dir < 4; ++dir)
{
    boolean[][] temp = new boolean[N][M];
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            temp[i][j] = sight[i][j];
        }
    }

    switch (mode) {
    // ...
    }

    backTracking(depth + 1);

    sight = temp;
}

 

switch 문을 제외하고 큰 흐름의 코드이다.

우선은 CCTV 리스트에 있던 depth번째 CCTV를 가져와, nowCCTV에 저장해두고,

이 정보를 이용하여 로직에 대입할 것이다.

 

그리고, for문은 총 4방향으로 회전을 할 것인데,

이 CCTV들이 0도, 90도, 180도, 270도로 도는 것을 생각하여 dir을 0, 1, 2, 3 으로 값이 주어지게 반복했다.

 

처음에는 temp라는 boolean 2차원 배열을 만드는데,

이 temp에는 switch문을 통해 sight[][] 배열이 수정되기 전, sight[][]의 초기 상태를 저장해둔다.

 

backTracking()으로 재귀 함수에 들어간 이후, sight를 다시 temp로 초기화 해준다.

그럼 for문이 다시 진행되어 회전된 이후 다시 기존 sight에서 작업을 거치고 backTracking()으로 넘어간다.

 

switch (mode) {
case 1:
{
    mainLogic(x, y, dir);
    break;
}
case 2:
{
    mainLogic(x, y, dir);
    mainLogic(x, y, dir + 2);
    break;
}
case 3:
{
    mainLogic(x, y, dir);
    mainLogic(x, y, dir + 3);
    break;
}
case 4:
{
    mainLogic(x, y, dir);
    mainLogic(x, y, dir + 2);
    mainLogic(x, y, dir + 3);
    break;
}
case 5:
{
    mainLogic(x, y, dir);
    mainLogic(x, y, dir + 1);
    mainLogic(x, y, dir + 2);
    mainLogic(x, y, dir + 3);
    break;
}
default :
    break;
}

 

위는 switch문이다.

mode에 따라서 1 ~ 5 의 case가 존재하고,

각각 감시하는 방향에 따라 mainLogic 함수를 돌려준다.

 

dx, dy를 회전하도록 (0, 1) / (-1, 0) / (0, -1) / (1, 0) 순으로 세팅해두었으므로,

for문에서 dir 에 따라 회전하는 로직이 잘 맞춰진다.

 

static void mainLogic(int x, int y, int dir)

static void mainLogic(int x, int y, int dir) {
    int d = dir % 4;
    int k = 0;

    while (true)
    {
        int nx = x + dx[d] * k;
        int ny = y + dy[d] * k;

        if (nx >= N || nx < 0 || ny >= M || ny < 0)
            break;

        if (map[nx][ny] == 6)
            break;

        sight[nx][ny] = true;
        k ++;
    }
}

 

위의 코드는 mainLogic으로, 정해진 방향으로 벽 또는 경계까지 sight[ ][ ] 값을 true로 바꿔주어,

감시구역을 일직선으로 늘려주는 메소드이다.

 

d 를 dir % 4로 하는 이유?

: 0 ~ 3으로 증가하는 dir에 방향에 따라 +1 (90도 우회전), +2 (180도 우회전), +3 (270도 우회전)

이 되어서 값이 들어오므로, 0 ~ 6 까지의 값이 들어올 수 있다.

이 값을 4로 나눈 연산을 해주면 우리가 원하는 방향을 정확히 지정할 수 있게 된다.

 

이렇게 sight 배열을 채워넣고 backTracking이 진행되면 결과가 나온다.

3. 코드 및 결론

[ 전체 코드 ]

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

public class Main {

    static int N;
    static int M;
    static int size;
    static int min = 2147483647;
    static int[][] map;
    static boolean[][] sight;
    static final int[] dx = {0, -1, 0, 1};
    static final int[] dy = {1, 0, -1, 0};
    static List <CCTV> cctvList;

    static class CCTV {
        int x;
        int y;
        int mode;

        public CCTV(int x, int y, int mode) {
            super();

            this.x = x;
            this.y = y;
            this.mode = mode;
        }
    }

    static void mainLogic(int x, int y, int dir) {
        int d = dir % 4;
        int k = 0;

        while (true)
        {
            int nx = x + dx[d] * k;
            int ny = y + dy[d] * k;

            if (nx >= N || nx < 0 || ny >= M || ny < 0)
                break;

            if (map[nx][ny] == 6)
                break;

            sight[nx][ny] = true;
            k ++;
        }
    }

    static void backTracking(int depth) {
        if (depth == size)
        {
            int res = 0;

            for (int i = 0; i < N; ++i)
            {
                for (int j = 0; j < M; ++j)
                {
                    if (!sight[i][j] && map[i][j] == 0)
                        res ++;
                }
            }

            if (res < min)
                min = res;

            return;
        }

        CCTV nowCCTV = cctvList.get(depth);
        int x = nowCCTV.x;
        int y = nowCCTV.y;
        int mode = nowCCTV.mode;

        for (int dir = 0; dir < 4; ++dir)
        {
            boolean[][] temp = new boolean[N][M];
            for (int i = 0; i < N; ++i)
            {
                for (int j = 0; j < M; ++j)
                {
                    temp[i][j] = sight[i][j];
                }
            }

            switch (mode) {
            case 1:
            {
                mainLogic(x, y, dir);
                break;
            }
            case 2:
            {
                mainLogic(x, y, dir);
                mainLogic(x, y, dir + 2);
                break;
            }
            case 3:
            {
                mainLogic(x, y, dir);
                mainLogic(x, y, dir + 3);
                break;
            }
            case 4:
            {
                mainLogic(x, y, dir);
                mainLogic(x, y, dir + 2);
                mainLogic(x, y, dir + 3);
                break;
            }
            case 5:
            {
                mainLogic(x, y, dir);
                mainLogic(x, y, dir + 1);
                mainLogic(x, y, dir + 2);
                mainLogic(x, y, dir + 3);
                break;
            }
            default :
                break;
            }

            backTracking(depth + 1);

            sight = temp;
        }
    }

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

        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        cctvList = new ArrayList<>();
        map = new int[N][M];
        sight = new boolean[N][M];

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

        size = cctvList.size();
        backTracking(0);
        System.out.println(min);
    }
}

 

[ 결론 ]

 

깊은 복사를 활용해서 temp배열을 복사 해둔 것이 핵심이었고,

방향을 불필요하게 탐색하는 부분이 있지만 이 부분은 추후 최적화 시에, 탐색안해도 되는 중복부분을 빼도 좋을 것 같다.

 

길고 긴 구현 문제였다. 이런 문제들을 풀 때는 조건들을 하나씩 정리해가며 어떤 방향으로 어떤 메소드를 쓸지,

다 체계적으로 정리하지 않으면 많이 꼬이는 것 같다. 많이 적으면서 풀자!