문제
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
설명
헷갈려서 엄청 오래 걸린 문제다...
근데 진짜 말그대로 1~5번까지 cctv를 90도씩 돌려가며 조합해서 사각지대의 최솟값을 구해야 한다.
방향을 바꾸는 과정은 시계방향으로 상 우 좌 하로 0, 1, 2, 3 순서이다.
(순서는 그냥 자기 마음대로 정해면 됨 나는 상우하좌가 편해서 저렇게 외웠다!)
CCTV는 1~5까지 총 5개의 형태가 있다.
각각의 경우를 90도 회전하는 경우를 생각해보면 아래와 같이 나타낼 수 있다.
1번의 경우 4가지, 2번 2가지, 3번 4가지, 4번 4가지, 5번 1가지의 경우가 나온다.
하지만 편의를 위해 상 우 하 좌 4방향이 있다고 가정하고, 방향이 있다면 1 없다면 0으로 나타낸다면
화살표 밑의 () 소괄호처럼 표현할 수 있다.
예를 들어 1번과 2번 CCTV를 가진 사무실이 있다면
1번 카메라로 나올 수 있는 방향 가짓수는 4,
2번 카메라로 나올 수 있는 방향 가지수는 2로 총 8가지의 경우의 수가 나오고
이 8가지를 바탕으로 감시를 하고, 가장 최소 사각지대를 가진 경우가 정답이 되는 것이다.
즉, 1~5까지의 CCTV가 가지는 방향에 대한 순열을 구한다고 생각하면 모든 경우를 구할 수 있다.
순열은 n개의 값 중에서 r개의 숫자를 순서대로 뽑는 경우를 말한다.
이를 적용해 4개의 방향 중에서 CCTV의 총 개수 r만큼을 순서대로 뽑아 나올 수 있는 모든 방향의 경우를 따져보는 것!
DFS를 이용해 순열을 구해준다.
예를 들어 1~3까지의 CCTV가 있다면
(0, 0, 0), (0, 0, 1) (0, 0, 2)... (0, 1, 1)... (1, 1, 1) ... (3, 3, 3)
1~5까지의 CCTV가 있다면
(0, 0, 0, 0, 0)... (0, 1, 2, 2, 3)... (3, 3, 3, 3, 3)
* 순열에 관해 더 자세히 알고 싶다면 아래 포스트 참고
[Java] 순열 Permutation
public static void permutation(int depth, int r) {
if(depth == r) {
// Copy original 'map' array
copyMap = new int[N][M];
for(int i = 0; i < map.length; i++) {
System.arraycopy(map[i], 0, copyMap[i], 0, map[i].length);
}
// cctv번호와 순열로 뽑혀진 방향에 맞는 상하좌우 방향 설정
for(int i = 0; i < cctvList.size(); i++) {
direction(cctvList.get(i), output[i]);
}
// 사각 지대 구하기
getBlindSpot();
return;
}
for(int i = 0; i < 4; i++) {
output[depth] = i;
permutation(depth+1, r);
}
}
depth가 r과 같아졌다는 것은 r만큼의 순열을 모두 뽑았다는 것.
이때 기존의 사무실을 구성하는 map 배열을 복사한다.
기존 map 배열은 건들지 말고, 복사한 배열에서 감시를 수행해 총 몇 개의 사각지대가 나오는지 판별한다.
그다음, direction 함수에서 CCTV번호에 맞는 방향을 지정한다.
// 각 cctv 번호와 순열로 뽑혀진 방향에 맞게 감시
public static void direction(CCTV cctv, int d) {
int cctvNum = cctv.num;
if(cctvNum == 1) {
if(d == 0) watch(cctv, 0); // 상
else if(d == 1) watch(cctv, 1); // 우
else if(d == 2) watch(cctv, 2); // 하
else if(d == 3) watch(cctv, 3); // 좌
} else if(cctvNum == 2) {
if(d == 0 || d == 2) {
watch(cctv, 0); watch(cctv, 2); // 상하
} else {
watch(cctv, 1); watch(cctv, 3); // 좌우
}
} else if(cctvNum == 3) {
if(d == 0) {
watch(cctv, 0); // 상우
watch(cctv, 1);
} else if(d == 1) {
watch(cctv, 1); // 우하
watch(cctv, 2);
} else if(d == 2) {
watch(cctv, 2); // 하좌
watch(cctv, 3);
} else if(d == 3) {
watch(cctv, 0); // 좌상
watch(cctv, 3);
}
} else if(cctvNum == 4) {
if(d == 0) {
watch(cctv, 0); // 좌상우
watch(cctv, 1);
watch(cctv, 3);
} else if(d == 1) {
watch(cctv, 0); // 상우하
watch(cctv, 1);
watch(cctv, 2);
} else if(d == 2) {
watch(cctv, 1); // 좌하우
watch(cctv, 2);
watch(cctv, 3);
} else if(d == 3) {
watch(cctv, 0); // 상좌하
watch(cctv, 2);
watch(cctv, 3);
}
} else if(cctvNum == 5) { // 상우하좌
watch(cctv, 0);
watch(cctv, 1);
watch(cctv, 2);
watch(cctv, 3);
}
}
CCTV의 번호와 뽑힌 방향에 맞게 감시를 한다.
watch 함수에 현재 CCTV 정보와 확인할 방향을 주어 본격적으로 감시를 수행한다.
// BFS로 방향에 맞게 감시
public static void watch(CCTV cctv, int d) {
Queue<CCTV> queue = new LinkedList<>();
boolean[][] visited = new boolean[N][M];
queue.add(cctv);
visited[cctv.x][cctv.y] = true;
while(!queue.isEmpty()) {
int nx = queue.peek().x + dx[d];
int ny = queue.poll().y + dy[d];
if(nx < 0 || nx >= N || ny < 0 || ny >= M || copyMap[nx][ny] == 6) { // 범위를 벗어나거나 벽을 만나면 끝
break;
}
if(copyMap[nx][ny] == 0) {
copyMap[nx][ny] = -1; // 빈칸이라면 감시할 수 있다는 의미로 -1
queue.add(new CCTV(cctv.num, nx, ny));
} else { // 다른 cctv가 있거나 이미 감시된 칸이라면
queue.add(new CCTV(cctv.num, nx, ny)); // 그냥 통과
}
}
}
BFS를 이용해 CCTV의 시작 위치에서부터 각 방향에 맞게 한 칸씩 이동한다.
범위를 벗어나거나 벽을 만나면 끝난다.
빈칸을 만나면 감시할 수 있기에 copyMap의 값을 -1로 만들어준다.
다른 CCTV를 만나거나 이미 감시된 칸이라면 그냥 통과하고 큐에 새로운 좌표만 넣어준다.
BFS가 모두 수행된 뒤에 copyMap을 순회하며 총 몇 개의 사각지대가 있는지 구하고, 최솟값을 정답으로 갱신한다.
전체 코드
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static int N, M;
public static int[][] map;
public static int[][] copyMap;
public static int[] output;
public static ArrayList<CCTV> cctvList;
public static int[] dx = {-1, 0, 1, 0}; // 상 우 하 좌 시계방향 순서
public static int[] dy = {0, 1, 0, -1};
public static int answer = Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
map = new int[N][M];
cctvList = new ArrayList<>();
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
map[i][j] = sc.nextInt();
if(map[i][j] != 0 && map[i][j] != 6) {
cctvList.add(new CCTV(map[i][j], i, j));
}
}
}
output = new int[cctvList.size()]; // 순열을 담을 배열
permutation(0, cctvList.size());
System.out.println(answer);
}
// DFS로 상하좌우 4방향 중에서 cctv의 총 개수, r만큼을 순서대로 뽑는 순열을 구함
public static void permutation(int depth, int r) {
if(depth == r) {
// Copy original 'map' array
copyMap = new int[N][M];
for(int i = 0; i < map.length; i++) {
System.arraycopy(map[i], 0, copyMap[i], 0, map[i].length);
}
// cctv번호와 순열로 뽑혀진 방향에 맞는 상하좌우 방향 설정
for(int i = 0; i < cctvList.size(); i++) {
direction(cctvList.get(i), output[i]);
}
// 사각 지대 구하기
getBlindSpot();
return;
}
for(int i = 0; i < 4; i++) {
output[depth] = i;
permutation(depth+1, r);
}
}
// 각 cctv 번호와 순열로 뽑혀진 방향에 맞게 감시
public static void direction(CCTV cctv, int d) {
int cctvNum = cctv.num;
if(cctvNum == 1) {
if(d == 0) watch(cctv, 0); // 상
else if(d == 1) watch(cctv, 1); // 우
else if(d == 2) watch(cctv, 2); // 하
else if(d == 3) watch(cctv, 3); // 좌
} else if(cctvNum == 2) {
if(d == 0 || d == 2) {
watch(cctv, 0); watch(cctv, 2); // 상하
} else {
watch(cctv, 1); watch(cctv, 3); // 좌우
}
} else if(cctvNum == 3) {
if(d == 0) {
watch(cctv, 0); // 상우
watch(cctv, 1);
} else if(d == 1) {
watch(cctv, 1); // 우하
watch(cctv, 2);
} else if(d == 2) {
watch(cctv, 2); // 하좌
watch(cctv, 3);
} else if(d == 3) {
watch(cctv, 0); // 좌상
watch(cctv, 3);
}
} else if(cctvNum == 4) {
if(d == 0) {
watch(cctv, 0); // 좌상우
watch(cctv, 1);
watch(cctv, 3);
} else if(d == 1) {
watch(cctv, 0); // 상우하
watch(cctv, 1);
watch(cctv, 2);
} else if(d == 2) {
watch(cctv, 1); // 좌하우
watch(cctv, 2);
watch(cctv, 3);
} else if(d == 3) {
watch(cctv, 0); // 상좌하
watch(cctv, 2);
watch(cctv, 3);
}
} else if(cctvNum == 5) { // 상우하좌
watch(cctv, 0);
watch(cctv, 1);
watch(cctv, 2);
watch(cctv, 3);
}
}
// BFS로 방향에 맞게 감시
public static void watch(CCTV cctv, int d) {
Queue<CCTV> queue = new LinkedList<>();
boolean[][] visited = new boolean[N][M];
queue.add(cctv);
visited[cctv.x][cctv.y] = true;
while(!queue.isEmpty()) {
int nx = queue.peek().x + dx[d];
int ny = queue.poll().y + dy[d];
// 범위를 벗어나거나 벽을 만나면 끝
if(nx < 0 || nx >= N || ny < 0 || ny >= M || copyMap[nx][ny] == 6) {
break;
}
if(copyMap[nx][ny] == 0) {
copyMap[nx][ny] = -1; // 빈칸이라면 감시할 수 있다는 의미로 -1
queue.add(new CCTV(cctv.num, nx, ny));
} else { // 다른 cctv가 있거나 이미 감시된 칸이라면
queue.add(new CCTV(cctv.num, nx, ny)); // 그냥 통과
}
}
}
// 사각 지대 구하기
public static void getBlindSpot() {
int cnt = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(copyMap[i][j] == 0) {
cnt++;
}
}
}
answer = Math.min(answer, cnt);
}
}
class CCTV {
int num;
int x;
int y;
CCTV(int num, int x, int y) {
this.num = num;
this.x = x;
this.y = y;
}
}GITHUB
KwonMinha/BOJ
Baekjoon Online Judge(Java) 문제풀이. Contribute to KwonMinha/BOJ development by creating an account on GitHub.
github.com
'알고리즘 문제 > 백준' 카테고리의 다른 글
| [백준 - Java] 2579번 : 계단 오르기 (0) | 2021.02.23 |
|---|---|
| [백준 - Java] 11057번 : 오르막 수 (0) | 2021.02.22 |
| [백준 - Java] 14499번 : 주사위 굴리기 (삼성 SW 역량 테스트 기출 문제) (0) | 2021.02.10 |
| [백준 - Java] 3190번 : 뱀 (삼성 SW 역량 테스트 기출 문제) (0) | 2021.02.09 |
| [백준 - Java] 1931번 : 회의실 배정 (0) | 2021.01.25 |
댓글