Skip to main content

15683 - 감시

info
  • 문제 보기: 15683 - 감시
  • 소요 시간: 53분 27초
  • 풀이 언어: java
  • 체감 난이도: 3️⃣
  • 리뷰 횟수: ✅

풀이 키워드​

스포주의

구현 dfs


풀이 코드​

info
  • 메모리: 36484 KB
  • 시간: 452 ms
import java.util.*;
import java.io.*;

public class Main
{
    static int n, m;
    static int[][] table;
    static List<int[]> cctvList;
    static int[] dy = new int[]{0, 1, 0, -1}; // R B L T
    static int[] dx = new int[]{1, 0, -1, 0};
    static int ans = 999;
    
    public static void mark(int y, int x, int d) { // fill -1 for reachable areas
        d %= 4;
        int ny = y;
        int nx = x;
        while (true) {
            ny += dy[d];
            nx += dx[d];
            if (ny < 0 || n <= ny || nx < 0 || m <= nx) return; // out of bound
            if (table[ny][nx] == 6) return; // wall
            if (table[ny][nx] != 0) continue; // cctv
            table[ny][nx] = -1;
        }
    }
    
    public static void dfs(int idx) {
        // base case
        if (idx >= cctvList.size()) {
            int cnt = 0;
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < m; ++j)
                    if (table[i][j] == 0) ++cnt;
            
            ans = cnt < ans ? cnt : ans;
            return;
        }
        
        // 1. pre-set value
        int[][] tableCpy = new int[n][m];
        int y = cctvList.get(idx)[0];
        int x = cctvList.get(idx)[1];
        
        // 2. mark areas
        for (int d = 0; d < 4; ++d) { // rotate clockwise: 0 -> R
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < m; ++j)
                    tableCpy[i][j] = table[i][j]; // deepcopy
            
            switch(table[y][x]) {
                case 1: mark(y, x, d); break;
                case 2: mark(y, x, d); mark(y, x, d+2); break;
                case 3: mark(y, x, d); mark(y, x, d+3); break;
                case 4: mark(y, x, d); mark(y, x, d+2); mark(y, x, d+3); break;
                case 5: mark(y, x, d); mark(y, x, d+1); mark(y, x, d+2); mark(y, x, d+3); break;
            }
            
            // 3. recursion
            dfs(idx+1);
            
            // 4. post-set value
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < m; ++j)
                    table[i][j] = tableCpy[i][j]; // deepcopy
        }
                
        return;
    }
    
    public static void main(String[] args) throws IOException {
        input();
        dfs(0);
        System.out.println(ans);
    }
    
    public static void input() 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());
        table = new int[n][m]; // init
        cctvList = new ArrayList<>(); // init
        
        for (int i = 0; i < n; ++i) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; ++j) {
                int value = Integer.parseInt(st.nextToken());
                if (0 < value && value < 6) cctvList.add(new int[]{i, j});
                table[i][j] = value;
            }
        }
    }
}

풀이 해설​

시간복잡도는 naive하게 따지면 O(4knm)O(4^knm) 쯤이다. (k(k: CCTV 개수 ≤8)\le 8)

나머지 내용은 WIP


📌 파라미터 할당 안됨 이슈​

mark 함수에서 처음에 이런식으로 ny, nx를 업뎃하다가 무한루프에 걸렸다.

while (true) {
    int ny = y + dy[d];
    int nx = x + dx[d];
    if (ny < 0 || n <= ny || nx < 0 || m <= nx) return; // out of bound
    if (table[ny][nx] == 6) return; // wall
    if (table[ny][nx] != 0) continue; // cctv
    table[ny][nx] = -1;
    y = ny;
    x = nx;
}

이유는 알아냈는데 추후 같은 실수하지 말라고 일부러 답 안써놓겠음 😉

알아서 맞춰보세요!


메모​

  • 시뮬 유형은 풀이 시간 줄이려면 효율성을 좀 포기하는게 맞는듯
    • 당장 5번 CCTV만 해도 쓸데없는 중복 연산이 들어가게 되는데... 이런거 따로 처리해주면 가독성 떨어짐