[백준] 감시

[hye-on]

🔗 감시

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>

using namespace std;

//1:15 ~2:12

//n이 작아서 완탐

int n, m;
int map[8][8];
int cctvCnt;
int cctvArea;

//방향을 비트마스크?

int cnt[] = { 0,4,2,4,4,1 }; // 2번은 2개 케이스 , 5번은 1개 케이스
vector<pair<int, int>>cctv; // 
string choice[9];

vector<vector<string>> dir = {
	{},
	{"1000", "0100", "0010", "0001"}, //1
	{"1100","0011"}, //2
	{"1001","1010","0101","0110"}, //3  상우, 상좌, 하우, 하좌
	{"1110","1101","1011","0111"}, //4
	{"1111"}  //5
};
// 0101 상하좌우 각 표시 
int dy[] = { -1,1,0,0 }; //상하좌우
int dx[] = { 0,0,-1,1 };

bool visit[8][8];

int cntOneDir(int dir, int idx) { //idx번째 cctv를 dir방향으로 검사
	int y = cctv[idx].first;
	int x = cctv[idx].second;

	int cnt = 0;
	while (true) {
		y += dy[dir];
		x += dx[dir];
		if (y >= n || y < 0 || x >= m || x < 0)
			break;
		if (map[y][x] == 6)
			break;
		if (!visit[y][x]) {
			//방문한 적 없고 빈칸이면 체크. 다른 cctv일 수도 있어서
			if(map[y][x]==0)
				cnt++;
			visit[y][x] = true;
		}
	}
	return cnt;
}
void cntArea() {
	//각 cctv마다 
	int sum = 0;
	
	for (int i = 0; i < cctvCnt; i++) {
		//4방향으로 검사
		for (int j = 0; j < 4; j++) {
			//그 방향으로 검사 가능하면
			if(choice[i][j]=='1')
				sum += cntOneDir(j, i);
		}
	}
	
	cctvArea = max(cctvArea, sum);
}

void backtraking(int depth) {
	if (depth == cctvCnt) {
		cntArea();
		memset(visit, false, sizeof(visit));
		return;
	}
	int cctvNum = map[cctv[depth].first][cctv[depth].second];
	int cctvCase = cnt[cctvNum];
	
	for (int i = 0; i < cctvCase; i++) {
		choice[depth] = dir[cctvNum][i];
		backtraking(depth + 1);
	}
}

int main() {


	cin >> n >> m;
	int answer = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] > 0 && map[i][j] < 6) {
				cctv.push_back({ i, j });
				cctvCnt++;		
			}
			if (map[i][j] == 0)
				answer++;
		}
	}

	backtraking(0);
	answer -= cctvArea;
	cout << answer;
	
}

코멘트

- 방향을 바꿔주고 탐색하는 부분을 좀 더 잘할 수 있는 방법이 있을까요 (코드 중복 없이) - 다른 사람 풀이 : 방향을 {0,2}로 세팅하고 for문 돌때 방향을 증가한다.

dir = (dir + i) % 4;:

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

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

public class Main
{
    // 11:39 START! 11:47 STOP!
    // 13:14 RESTART! 
    /**
     *  완탐? O(4^n) 이고 n의 최댓값이 8이기 때문에 OK
     */
    static int n, m, numOfCctv;
    static int[][] room;
    static int[] selected;
    static int answer = Integer.MAX_VALUE;
	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		room = new int[n][m];
	        numOfCctv = 0;
		for(int i = 0; i < n; ++i) {
		    st = new StringTokenizer(bf.readLine());
		    for(int j = 0; j < m; ++j) {
		        room[i][j] = Integer.parseInt(st.nextToken());
		        
		        if(room[i][j] >= 1 && room[i][j] <= 5) {
		            numOfCctv++;
		        }
		    }
		}
		
		selected = new int[numOfCctv]; // 방향 정하기
		dfs(0);
		
		System.out.println(answer);
	}
	
	public static void dfs(int level) {
	    if(level == numOfCctv) {
	        int[][] copy = new int[n][m];
	        for(int i = 0; i < n; ++i) {
	            for(int j = 0; j < m; ++j) {
	               copy[i][j] = room[i][j];
	            }
	        }
	        
	        int idx = 0;
	        for(int i = 0; i < n; ++i) {
	            for(int j = 0; j < m; ++j) {
	               if(copy[i][j] >= 1 && copy[i][j] <= 5) {
	                   check(i, j, selected[idx], copy);
	                   idx++;
	               } 
	            }
	        }
	        
	        int count = 0;
	        for(int i = 0; i < n; ++i) {
	            for(int j = 0; j < m; ++j) {
	               if(copy[i][j] == 0) {
	                   count++;
	               } 
	            }
	        }
	        
	        answer = Math.min(answer, count);
	        return;
	    }
	    
	    for(int i = 0; i < 4; ++i) {
	        selected[level] = i;
	        dfs(level + 1);
	    }
	}
	
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	public static void check(int x, int y, int d, int[][] room) {
	    int type = room[x][y];
	    if(type == 1) {
	        fill(x, y, d, room);
	        return;
	    }
	    
	    if(type == 2) {
	        fill(x, y, d, room);
	        fill(x, y, (d + 2) % 4, room);
	        return;
	    }
	    
	    if(type == 3) {
	        fill(x, y, d, room);
	        fill(x, y, (d + 1) % 4, room);
	    }
	    
	    if(type == 4) {
	        fill(x, y, d, room);
	        fill(x, y, (d + 1) % 4, room);
	        fill(x, y, (d + 2) % 4, room);
	    }
	    
	    if(type == 5) {
	        fill(x, y, d, room);
	        fill(x, y, (d + 1) % 4, room);
                fill(x, y, (d + 2) % 4, room);
                fill(x, y, (d + 3) % 4, room);
	    }
	}
	
	public static void fill(int x, int y, int d, int[][] room) {
	    int nx = x + dx[d];
            int ny = y + dy[d];
        
        while(nx >= 0 && nx < n && ny >= 0 && ny < m && room[nx][ny] != 6) {
            if(room[nx][ny] == 0) {
                room[nx][ny] = -1;
            }

            x = nx;
            y = ny;
            nx = x + dx[d];
            ny = y + dy[d];
        }
    }
	
}

코멘트