15683 - 감시

정보

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

풀이 키워드

스포주의

구현 dfs

풀이 코드

정보

• 메모리: 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(4^knm)$ 쯤이다. $(k$: CCTV 개수 $\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만 해도 쓸데없는 중복 연산이 들어가게 되는데... 이런거 따로 처리해주면 가독성 떨어짐