https://www.acmicpc.net/problem/15683
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
[문제]
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.
1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.
CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다. CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0
지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.
CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 칸을 감시할 수 없다.
0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5
위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.
CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.
0 0 2 0 3
0 6 0 0 0
0 0 6 6 0
0 0 0 0 0
위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.
# # 2 # 3
0 6 # 0 #
0 0 6 6 #
0 0 0 0 #
사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.
[입력 조건]
- 첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)
- 둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.
- CCTV의 최대 개수는 8개를 넘지 않는다.
[코드]
import java.util.*;
class CCTV {
int num,x,y;
public CCTV(int num, int x, int y) {
this.num=num;
this.x=x;
this.y=y;
}
}
public class BaekJoon_15683 {
static int[][] map,temp;
static int[] output;
static int n,m,result=Integer.MAX_VALUE;
static ArrayList<CCTV> arr=new ArrayList<>();
// CCTV는 시계방향으로 방향을 바꾸기 때문에 상,우,하,좌 순
static int[] dx= {-1,0,1,0};
static int[] dy= {0,1,0,-1};
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
map=new int[n][m];
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
map[i][j]=sc.nextInt();
// CCTV가 있는 좌표와 CCTV 번호 저장
if(map[i][j]!=0&&map[i][j]!=6)
arr.add(new CCTV(map[i][j],i,j));
}
}
output=new int[arr.size()];
choose_direction(0,arr.size());
System.out.println(result);
}
/*
* 각 CCTV는 상,하,좌,우 4방향을 선택할 수 있다. 이런 CCTV가 여러개가 존재할 경우
* 각 CCTV가 바라볼 수 있는 방향의 조합마다 사각지대의 개수를 갱신해주어야 하기 때문에
* 모든 CCTV가 바라볼 수 있는 방향의 조합을 DFS를 사용하여 구한다.
*
* 이때 1번 CCTV가 회전하면서 생기는 방향의 가지수는 4개, 2번 CCTV는 2개,
* 3번, 4번 CCTV는 4개, 5번 CCTV는 1개이다.
*
* 예를들어 1번, 2번 cctv가 한개씩 설치되어 있다고 가정해보자.
* 총 나올 수 있는 방향의 가짓수는 4(1번)*2(2번)=8가지이다. 이 8가지를 모두 탐색해 사각지대의 개수를 갱신해주면 된다.
*/
static void choose_direction(int depth, int num) {
// 재귀의 깊이가 설치된 cctv의 개수와 같아졌다면
if(depth==num) {
// 배열 복사
temp=new int[n][m];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
temp[i][j]=map[i][j];
// cctv의 정보와 해당 cctv가 바라보고 있는 방향으로 cctv 작동
for(int i=0;i<arr.size();i++)
operate_CCTV(arr.get(i),output[i]);
count_blind(); // 사각지대 개수 count
return;
}
for(int i=0;i<4;i++) {
/*
* 방향 저장
* 0:상, 1:좌, 2:하, 3:우
*/
output[depth]=i;
choose_direction(depth+1,num);
}
}
// cctv 번호와 바라보고 있는 방향으로 감시
static void operate_CCTV(CCTV cctv, int dir) {
int number=cctv.num;
// 1번 cctv
if(number==1) {
if(dir==0) watch(cctv,0); // 상
else if(dir==1) watch(cctv,1); // 우
else if(dir==2) watch(cctv,2); // 좌
else if(dir==3) watch(cctv,3); // 하
}
// 2번 cctv
else if(number==2) {
if(dir==0||dir==2) { // 상하
watch(cctv,0);
watch(cctv,2);
}
else { // 좌우
watch(cctv,1);
watch(cctv,3);
}
}
// 3번 cctv
else if(number==3) {
if(dir==0) { // 상우
watch(cctv,0);
watch(cctv,1);
}
else if(dir==1){ // 우하
watch(cctv,1);
watch(cctv,2);
}
else if(dir==2){ // 하좌
watch(cctv,2);
watch(cctv,3);
}
else if(dir==3){ // 좌상
watch(cctv,3);
watch(cctv,0);
}
}
// 3번 cctv
else if(number==4) {
if(dir==0) { // 좌상우
watch(cctv,3);
watch(cctv,0);
watch(cctv,1);
}
else if(dir==1){ // 상우하
watch(cctv,0);
watch(cctv,1);
watch(cctv,2);
}
else if(dir==2){ // 좌하우
watch(cctv,1);
watch(cctv,2);
watch(cctv,3);
}
else if(dir==3){ // 상좌하
watch(cctv,2);
watch(cctv,3);
watch(cctv,0);
}
}
// 3번 cctv
else { // 상우좌하
watch(cctv,0);
watch(cctv,1);
watch(cctv,2);
watch(cctv,3);
}
}
// 해당 방향으로 cctv에 의해 감시되는 지역을 -1로 변환한다.
public static void watch(CCTV cctv, int d) {
Queue<CCTV> q=new LinkedList<>();
q.add(cctv);
while(!q.isEmpty()) {
CCTV c=q.poll();
int nx=c.x+dx[d];
int ny=c.y+dy[d];
// 범위를 벗어나거나 벽을 만나면 끝
if(nx<0||nx>=n||ny<0||ny>= m||temp[nx][ny]==6)
break;
// 아직 감시되지 않은 지역이라면
if(temp[nx][ny]==0) {
temp[nx][ny]=-1; // 감시됨을 표시
q.add(new CCTV(cctv.num,nx,ny));
}
/*
* 다른 cctv가 있거나 이미 다른 ccvt에 의해 감시가 된 칸이라도
* 해당 칸을 넘어갈 수 있으므로 탐색을 위해 큐에 삽입
*/
else
q.add(new CCTV(cctv.num,nx,ny));
}
}
// 사각지대의 개수를 count하는 함수
static void count_blind() {
int count=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(temp[i][j]==0)
count++;
result=Math.min(result, count);
}
}
[고찰]
이번 문제는 스스로 풀어보려 노력했지만 쉽지 않아 다른 사람의 코드를 참고하여 해결하였다. 문제가 복잡하고 조건이 많아 우선 문제의 구조화를 해보았다.
*** 1) 방향의 조합(choose_direction 함수)
1-1) CCTV 90만큼 회전할 수 있기 때문에 각 CCTV는 4가지의 경우의 수를 갖는다. 이때 2번 CCTV는 0도와 180도, 90도와 270도의 경우의 수가 같기 때문에 2가지의 경우의 수를 갖는다.
1-2) 이렇게 각 CCTV는 상, 하, 좌, 우 4방향을 선택할 수 있다. 이런 CCTV가 여러개가 존재할 경우 각 CCTV가 바라볼 수 있는 방향의 조합마다 사각지대의 개수를 갱신해주어야 한다.
1-3) DFS 알고리즘을 사용하여 각 CCTV의 방향을 바꿔주면서 모든 조합의 경우를 탐색한다.
*** 2) 각 CCTV 마다 감시 방향 설정(operate_CCTV 함수)
2-1) 탐색하고자 하는 CCTV의 번호와 방향에 따라 CCTV가 감시할 수 있는 지역을 체크하는 watch 함수를 호출한다.
*** 3) CCTV의 방향대로 감시한 곳 체크(watch 함수)
3-1) CCTV의 정보와, 현재 탐색하고자 하는 방향을 매개변수로 입력 받아 CCTV의 위치로 부터 해당 방향으로 감시를 시작한다.
3-2) 감시하고자 하는 곳이 배열 범위 외거나, 벽이라면 해당 CCTV의 감시를 종료한다.
3-3) 감시하고자 하는 곳의 배열 값이 0이라면 감시가 됐다는 의미로 배열 값을 변경(-1)한다. 만약 배열 값에 6이나(벽), 다른 CCTV에 의해 감시가 된 구역(-1)이더라고 해당 CCTV는 지나갈 수 있으므로 탐색을 위해 큐에 삽입한다.
이번 문제는 여태까지 풀어봤던 삼성 기출문제 중 가장 코드 줄이 길었던 문제였던 것 같다. 문제 자체의 난이도는 많이 어렵지는 않았지만 방향의 조합을 생각해내는 것과, 함수의 짜임새를 구성하는 것이 복잡해 어렵게 느껴졌던 것 같다.
'백준' 카테고리의 다른 글
| [백준_21610번 ] 마법사 상어와 비바라기_삼성 SW 역량테스트 (0) | 2021.09.07 |
|---|---|
| [백준_1525번] 퍼즐 (0) | 2021.09.03 |
| [백준_14500번] 테트로미노_삼성 SW 역량테스트 (0) | 2021.09.03 |
| [백준_2234번] 성곽 (0) | 2021.09.01 |
| [백준_15666번] N과 M (12) (0) | 2021.09.01 |