1. 문제에 대하여 📦

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

(1) 조건 분석 📊

상남자의 문제 완전탐색이다.
그냥 문제 조건 그대로 시간복잡도 신경 안쓰고 풀면 된다.
'오류가 없다면' 순열과 조합을 써도 문제가 풀려야 한다.

2. 코드가 나오기까지 🛠️

KEY WORD: 순열, 완전 탐색


1번	2번	3번	4번	5번

출처: 해당 문제의 이미지 사진

A. 순열은 어디에 쓰는가?

순열은 CCTV가 동작할 수 있는 모든 경우의 수를 세기 위하여 필요로 되어진다.

위에 나오는 각 CCTV는 90도씩 회전이 가능하다. 1,3,4번은 동서남북 모두 경우의 수가 다르고, 2번은 상하, 좌우만 다르며 5번에서는 나올 수 있는 경우의 수가 딱 하나이다. cctv는 1개 이상 8개 이하일 수 있기 때문에, CCTV가 바라보고 있는 방향에 따라 경우의 수가 무궁무진하게 나뉠 수 있다. 우리는 이걸 배열에 담아서 표현할 것이다.

즉 index = cctv의 번호, value는 0~3번까지 상하좌우를 나타낸다. (2번의 경우 0이 상하, 1이 좌우, 5번은 무조건 0만 존재), 여기서 조합이 아닌 이유가 들어난다. 왜냐면 배열간의 서로 value값을 바꾸면, CCTV마다 바라보는 방향이 달라져서 아예 새로운 경우의 수가 되기 떄문이다.

B. 완전탐색에 대하여

반복문으로 나타내기

CCTV가 바라봐야 하는 방향, CCTV의 위치, 유형을 알려주면, 해당 방향에 해당하는 모든 지점을 벽이나 벗어날 때까지 방문처리 해버리면 된다.
이후 전체 배열 값에서 아직도 값이 0인 지점 (즉 사각지대)의 개수를 세서 그 개수가 가장 작을 때를 찾아내 출력하면 된다.

(1) 시간복잡도 분석 ⏳

N,M <= 8, CCTV = 8

해당 문제에서 최악의 경우로 4가지 방향이 다 다른 1,3,4번 CCTV가 8개 주어졌다고 쳐보자.

모든 경우의 수 찾기 $O(4^8)$
각 경우의 수마다 값을 입력할 2차원 배열 만들기 $O(N^2)$
각 경우의 수마다 방문처리: 최대 $O(N^2)$
각 경우의 수마다 사각지대 세기 $O(N^2)$

한 개의 경우의 수마다 2차원 배열 만들기 + 방문처리 + 사각지대 세기가 병렬적으로 일어난다.
즉 이를 종합한 최악의 경우의 수는 $O(4^8 * (3N2))$ 이다. N도 8이라고 치면
$O(4^8 * (34^{2}))$ 이다.

즉 3,145,728의 연산횟수를 필요로 해서, 10^{8}이 맥시멈인 알고리즘 문제에서 가능하다.

3. 코드 🌐

(1) SUDO CODE 💬

+ 0. CCTV 좌표와 타입 저장하는 클래스 만들기
+ 1. 모든 CCTV에 대해서 그것의 동작 경우의 수 세기
-    (1) 하나의 경우의 수마다 전체 입력을 복사한 2차원 배열 새로 만들기
-    (2) 해당 배열에 대해서 CCTV가 바라보는 지점 전체 방문 처리하기
-    (3) 그럼에도 보지 못한 사각지대 개수 세기
-    (4) 이전까지 중 사각지대 최소값과 비교 후 이번 것이 더 작다면 갱신

(2) JAVA CODE ☕

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

public class Main{

    static class Coordinate{
        int r;
        int c;
        int type;

        public Coordinate(int r, int c){
            this.r = r;
            this.c = c;
        }

        public Coordinate (int r, int c, int type){
            this.r = r;
            this.c = c;
            this.type = type;
        }

        @Override
        public boolean equals(Object obj) {
            if(obj.getClass() != this.getClass()) return false;
            Coordinate o = (Coordinate) obj;
            return o.r == this.r && o.c == this.c;
        }

        @Override
        public int hashCode() {
            return this.r* 10 + this.c;
        }
    }
    static int N,M, min = Integer.MAX_VALUE;
    static int [][] field;
    static int [][] dir = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}}; //  상하좌우
    static ArrayList<Coordinate> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        init();
        permutation(new int[list.size()], 0);
        System.out.println(min);
    }

    public static void init() 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());
        field = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                field[i][j] = Integer.parseInt(st.nextToken());
                if(field[i][j] != 0 && field[i][j] != 6) {
                    list.add(new Coordinate(i,j, field[i][j]));
                }
            }
        }
    }

    public static void permutation (int [] nums, int depth ){
        if(depth == list.size()){
            int [][] map = new int [N][M];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    map[i][j] = field[i][j];
                }
            }
            for (int i = 0; i < list.size(); i++) {
                switch (list.get(i).type){
                    case 1: {
                        cctv1(nums[i], map,list.get(i));
                        break;
                    }
                    case 2:{
                        cctv2(nums[i], map, list.get(i));
                        break;
                    }
                    case 3: {
                        cctv3(nums[i], map, list.get(i));
                        break;
                    }
                    case 4: {
                        cctv4(nums[i], map,list.get(i));
                        break;
                    }
                    case 5: {
                        cctv5(map, list.get(i));
                        break;
                    }
                }
            }
            int cnt = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if(map[i][j] == 0) cnt++;
                }
            }
            min = Math.min(min, cnt);
            return;
        }
        Coordinate now = list.get(depth);
        int type = field[now.r][now.c];
        int max = type == 5? 1 :
            type == 2? 2: 4;

        for (int i = 0; i < max; i++) {
            nums[depth] = i;
            permutation(nums, depth+1);
        }
    }





    static void cctv1(int d, int [][] map, Coordinate coordinate) {
        int nextR = coordinate.r;
        int nextC = coordinate.c;
        visit(d,map, nextR, nextC,1);
    }

    static void cctv2(int d, int[][] map, Coordinate coordinate) {
        int nextR = coordinate.r;
        int nextC = coordinate.c;
        if(d == 0) { // 좌우
            visit(2,map, nextR, nextC,2);
            nextR = coordinate.r;;
            nextC = coordinate.c;
            visit(3, map, nextR, nextC,2);
        }else if (d == 1) { // 상하
            visit(0,map, nextR, nextC,2);
            nextR = coordinate.r;
            nextC = coordinate.c;
            visit(1, map, nextR, nextC,2);
        }
    }

    static void cctv3(int d, int[][] map, Coordinate coordinate){
        int nextR = coordinate.r;
        int nextC = coordinate.c;
        switch (d){ // 각각 90도씩
            case 0: {
                visit(0, map, nextR, nextC,3);
                nextR = coordinate.r;
                nextC = coordinate.c;
                visit(3, map, nextR, nextC,3);
                break;
            }
            case 1:{
                visit(0, map, nextR, nextC,3);
                nextR = coordinate.r;
                nextC = coordinate.c;
                visit(2, map, nextR, nextC,3);
                break;
            }
            case 2: {
                visit(1, map, nextR, nextC,3);
                nextR = coordinate.r;
                nextC = coordinate.c;
                visit(2, map, nextR, nextC,3);
                break;
            }
            case 3:{
                visit(1, map, nextR, nextC,3);
                nextR = coordinate.r;
                nextC = coordinate.c;
                visit(3, map, nextR, nextC,3);
            }
        }
    }
    static void cctv4(int d, int [][] map, Coordinate coordinate){
        int nextR = coordinate.r;
        int nextC = coordinate.c;
        switch (d){
            case 0: { // 좌상우
                visit(0, map, nextR, nextC, 4); // 상
                nextR = coordinate.r;
                nextC = coordinate.c;
                visit(2, map, nextR,nextC, 4);
                nextR = coordinate.r;
                nextC = coordinate.c;
                visit(3, map, nextR,nextC, 4);
                break;
            }
            case 1: { // 상, 하, 좌
                visit(0, map, nextR, nextC, 4); // 상
                nextR = coordinate.r;
                nextC = coordinate.c;
                visit(1, map, nextR,nextC, 4);
                nextR = coordinate.r;
                nextC = coordinate.c;
                visit(2, map, nextR,nextC, 4);
                break;
            }
            case 2: { // 상,하,우
                visit(0, map, nextR, nextC, 4); // 상
                nextR = coordinate.r;
                nextC = coordinate.c;
                visit(1, map, nextR,nextC, 4);
                nextR = coordinate.r;
                nextC = coordinate.c;
                visit(3, map, nextR,nextC, 4);
                break;
            }
            case 3: { // 하,좌,우
                visit(1, map, nextR, nextC, 4); // 상
                nextR = coordinate.r;
                nextC = coordinate.c;
                visit(2, map, nextR,nextC, 4);
                nextR = coordinate.r;
                nextC = coordinate.c;
                visit(3, map, nextR,nextC, 4);
                break;
            }

        }
    }

    static void cctv5(int[][] map, Coordinate coordinate){
        int nextR = coordinate.r;
        int nextC = coordinate.c;
        visit(0, map, nextR, nextC,5);
        nextR = coordinate.r;
        nextC = coordinate.c;
        visit(1, map, nextR, nextC,5);
        nextR = coordinate.r;
        nextC = coordinate.c;
        visit(2, map, nextR, nextC,5);
        nextR = coordinate.r;
        nextC = coordinate.c;
        visit(3, map, nextR, nextC,5);
    }

    public static void visit (int d, int [][] map, int nextR, int nextC, int type) {
        while (!OOB(nextR, nextC)){
            if( map[nextR][nextC] == 6) break;
            map[nextR][nextC] = type;
            nextR += dir[d][0];
            nextC += dir[d][1];
        }
    }

    public static boolean OOB(int r, int c){
        return r < 0 || c < 0 || r >= N || c >= M;
    }
}