[백준 15683번 / java] 감시

문제

15683번: 감시 (acmicpc.net)

cctv 방향 조합했을 때, N*M방의 cctv 사각지대 최소 크기 구하기

1. cctv번호에 따라 감시 가능한 방향이 다르다.

2. 해당 방향에 있는 칸 전체 감시 가능

3. 벽 통과하여 감시 불과, cctv는 통과 가능

4. cctv는 90도 회전 가능

5. 0=빈칸 6=벽 1~5=cctv

풀이

• 알고리즘 선택 :

각 cctv의 모든 방향 조합을 고려해서 최솟값을 구해야 한다. -> 완전 탐색

입력 범위가 1~8로 작으므로 완전탐색이 가능할 것이라고 판단했다.

 

• 대략적인 아이디어 :

예를 들어 1번, 2번, 3번 cctv가 존재하는 경우:

1번에서 4가지 중 한 가지 방향을 정해서 감시 가능한 모든 좌표를 board에 표시

-> 2번에서 2가지 중 한 가지 방향을 정해서 감시 가능한 모든 좌표를 board에 표시

-> 3번에서 4가지 중 한 가지 방향을 정해서 감시 가능한 모든 좌표를 board에 표시

모든 cctv를 다 고려했으므로 완성된 board에서 사각지대 개수를 구해 min과 비교, min을 업데이트.

 

위와 같은 과정이 각 cctv의 모든 방향의 조합을 만족할 때까지 반복된다. -> 재귀로 구현

(위의 경우 4*2*3=24가지 경우를 모두 고려해야 한다.)

 

• 코드 설계 :

dir[][][]에 cctv별 회전 방향을 dx, dy로 표현하여 전역으로 정의해둔다.

board[][] 에 입력값을 받는 동시에 cctv 리스트에 Node(x, y, cctv종류)를 채운다.

재귀함수를 시행한다 :

cctv리스트에서 인자로 전달받은 k번째 cctv를 꺼내 node변수에 저장. (처음 호출할 때는 0번째 cctv여야 하므로 0 전달)

node에서 x, y, type을 알아내서 변수로 저장.

k번째 cctv의 첫 번째 방향 선택한다.

board에 감시 가능한 곳 모두 표시한다 :

무한 반복문으로 dx, dy를 현재 노드의 x, y에 계속 더한다. 더 이상 진행 불가하다면 반복문을 탈출한다.

k+1번째 cctv를 재귀호출한다.

코드

 

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

public class boj_15683 {
    static int[][][] dir = {
            {{0, 1}, {1, 0}, {0, -1}, {-1, 0}},
            {{0, 1, 0, -1}, {1, 0, -1, 0}},
            {{-1, 0, 0, 1}, {0, 1, 1, 0}, {0, -1, 1, 0}, {0, -1, -1, 0}},
            {{-1, 0, 0, 1, 0, -1}, {1, 0, -1, 0, 0, 1}, {0, 1, 0, -1, 1, 0}, {0, -1, 1, 0, -1, 0}},
            {{0, 1, 1, 0, 0, -1, -1, 0}}
    };
    static List<Node1> cctv;
    static int[][] board;
    static int N, M;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        //board에 값을 받는 동시에 cctv 리스트 채우기
        board = new int[N][M];
        cctv = new ArrayList<>();
        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(board[i][j]>=1 && board[i][j] <=5)
                    cctv.add(new Node1(i, j, board[i][j]));
            }
        }
        recur(0);
        bw.write(min+" ");
        bw.close();
    }
    static void recur(int k){
        //재귀호출 탈출 조건: cctv리스트를 끝까지 다 돌았다면 (k==cctv.size()) 사각지대 개수를 리턴
        if(k == cctv.size()){
            int count = 0;
            for(int i=0; i<N; i++){
                for(int j=0; j<M; j++){
                    if(board[i][j] != 0)
                        count++;
                }
            }
            int ans = N*M - count;
            if(ans < min)
                min = ans;
            return;
        }

        //cctv리스트에서 k번째 cctv를 꺼냄
        //type을 통해 dx, dy를 찾음
        //dir배열을 참고하여 모든 회전하는 경우를 진행
        //감시 완료된 곳을 -1로 표시하여 board를 업데이트 -> monitor함수
        //k+1번째 cctv를 재귀호출
        Node1 node = cctv.get(k);
        int type = node.type;
        int[][] tmp = copy(board);
        for(int i=0; i<dir[type-1].length; i++){ //k번째 cctv의 i번째 방향
            for(int j=0; j<dir[type-1][i].length; j+=2){ //i번째 방향에 정의된 j번째 원소
                int dx = dir[type-1][i][j];
                int dy = dir[type-1][i][j+1];
                monitor(node, dx, dy); //node기준으로 dx, dy방향으로 감시할 때 감시 가능한 곳 표시
            }
        recur(k+1); //k번째 cctv의 i번째 방향을 진행한 후 k+1번째 cctv의 i번째 방향을 진행하러 재귀
        board = copy(tmp); //분기 후 원래 board 상태로 복원
        }
    }
    static void monitor(Node1 node, int dx, int dy){
        int newX = node.x;
        int newY = node.y;
        while(true){
            newX += dx;
            newY += dy;
            //board범위 밖으로 나가는 경우
            if(newX<0 || newX>=N || newY<0 || newY>=M)
                break;
            //벽을 만나는 경우
            if(board[newX][newY] == 6)
                break;
            //cctv를 만나거나 이미 감시한 경우
            if(board[newX][newY] != 0)
                continue;
            board[newX][newY] = -1;
        }
    }
    static int[][] copy(int[][] arr){
        //arr배열과 동일한 배열을 새로 생성하여 리턴
        int[][] ret = new int[N][M];
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                ret[i][j] = arr[i][j];
            }
        }
        return ret;
    }

}
class Node1 {
    int x, y, type;
    public Node1(int x, int y, int type){
        this.x = x;
        this.y = y;
        this.type = type;
    }
}

Note

• 굉장히 오래 걸렸던 문제이다.
• 처음에 알고리즘을 선택할 때 완탐으로 해가 될 수 있는 모든 경우를 찾아야 하고, 백트래킹으로 조합을 구성해야 하는 것까지는 판단했다.
• 그러나 시간복잡도 측면에서 통과 가능할지 판단하기 어려웠다. 그래서 완전탐색의 시간복잡도에 관해 공부했다.
• 이전에 풀었던 브루트 포스 완탐 문제에서는 재귀함수 호출 시 인자로 현재 상태를 전달하면서 depth를 더해갔다.
• 그리고 마지막 depth에 다다르면 재귀를 탈출하도록 재귀함수 시작 부분에 조건을 생성했다.
• 이 문제도 완전탐색이므로 그 구조를 똑같이 적용하면 되겠다는 생각까지는 해냈다.
• 그러나 cctv의 모든 방향 조합을 어떻게 코드로 표현할 것인지는 혼자 생각해내지 못했다.
• 보통 행렬을 탐색할 때는 다차원 배열로 모든 경우를 일일이 정의해두고 갖다쓰는 방법을 쓰는 것 같다. 
• 처음에는 int[] c의 cctv리스트와 같은 인덱스에 cctv 번호를 저장하고, wall 리스트도 생성하려고 했다. 
• 그리고 cctv리스트를 2차원 리스트로 만들어서 각 cctv마다 회전방향 수대로 방문체크를 만들려고 했다.
• 정답 코드를 다 이해한 후 백지에 다시 짜고, 틀린 부분을 디버깅하며 하나 하나 고쳐나가니 내가 어떤 부분에서 헷갈려하는지 알 수 있었다. 
• 3차원 배열 dir의 인덱스에 접근할 때 for문의 i, j가 dir의 어떤 요소에 접근하는지 헷갈려서 한참 고쳤다.
• 재귀 호출 후에 새로운 board를 생성하는 것도 아직까지 깔끔하게 이해되지 않았다. board를 재귀 인자로 전달해야 되는 거 아닐까 생각했는데, 재귀호출을 하면 dfs로 재귀 탈출 조건까지 만족하는 부분까지 찍고 그 다음 코드(board = copy(tmp))로 넘어가는 거라고 이해하니까 쉽다. 나중에 직접 디버깅하면서 맞는지 봐야겠다.
• 처음에 문제를 잘못 이해해서 나중에 이 부분이 이중for문의 바깥쪽이 아니라 안쪽에 위치하도록 고쳤다. cctv1의 모든 방향을 고려한 후 cctv2로 넘어가는 게 아니라, cctv1의 한 방향을 선택해서 감시동작을 시행한 후 cctv2로 넘어가야 한다.
• 사각지대 개수를 세어서 min으로 삽입하는 실수도 했다. 
• 스터디 피드백 : 재귀호출하기 전에 백트래킹할 때, tmp에 board를 복사해놓은 후, 재귀호출을 통해 board를 사용하고 다시 tmp에 저장해뒀던 상태로 board를 돌려놓는다. 해당 부분이 이해가 가지 않아 얘기를 나누었다.
• static으로 정의해둔 board를 직접 사용하는 것이 아니라 tmp에 복사한 배열을 통째로 재귀로 넘기는 식으로 사용하면 더 좋을 것 같아보였다. (이후에 14502 연구소 풀 때 적용하였음)

완전탐색 시간복잡도 

• 완탐은 가능한 모든 경우를 다 체크해서 정답을 찾는 것이므로, 무조건 문제 해결이 가능하지만 일반적으로 효율적이지 않은 방식이다. 
• 완전탐색으로 풀기 위해 고려할 점?
  ★ 주의 : 입력 개수가 작을 때가 좋다. 보통 O(2^N) 또는 O(N!)이기 때문.
  ★ 팁 : 이럴 때 완탐을 쓰자! 1)답의 범위가 작음 2)임의의 답이 조건을 만족하는지 역추적할 수 있음
  ★  아래 다섯가지 방법을 다 고려한다.
  
  1. Brute Force 
     • 반복/조건문으로 모두 테스트
  2. 순열(Permutation)
     • n개의 원소 중 r개를 중복 허용 없이 나열하는 경우의 수
  3. 재귀호출 
     • 필요한 것: 탈출 조건, 현재 함수의 상태를 전달하는 Parameter
     • 각 원소가 두 가지 상태만을 가질 때 사용하면 좋음. 
       • 포함 되면 해당 원소를 넣고, 함수 호출
       • 포함 안 되면 안 넣고 함수 호출
  4. 비트마스크
     • 이진수 표현기법 사용
       • 각 원소가 두 가지 상태만을 가질 때 사용
         • 예) 원소 n개인 집합의 모든 부분합을 구할 때, 각 원소가 포함되는지 아닌지를 1, 0으로 배열에 저장
     • BFS와 DFS
       • 그래프 자료구조에서 모든 정점을 탐색할 때.
         • 한 요소를 방문하고, 그 요소에 인접한 모든 요소를 우선 방문하는 방식
         • 주로 길찾기 문제에 사용

DP vs 재귀호출

• DP도 Top-Down 사용 시 재귀호출을 수행한다! 
  기저 사례를 통해 탈출 조건을 만들고 현재 함수 상태를 Parameter로 전달한다.
  return값을 정답 구하는 연산에 사용한다.
  
  
• DP 재귀
  • 작은 문제가 큰 문제와 동일한 구조
  • 큰 문제 해결 시 작은 문제의 결과를 기억했다가 그대로 사용
• 완탐 재귀
  • 크고 작은 문제의 구조가 다름
  • 이전 결과를 반드시 기억하지 X
  • 해결 가능한 방법을 모두 탐색하는 경우 사용