[DFS/구현] 백준 15683번 감시 - JAVA

 

쉬울 줄 알고 덤볐다가 구현력에 한계를 느낀 문제이다.

알고보니 삼성 기출문제였다는 소리를 본 것 같다 ^__^...

 

 

---

1. 출처

---

 

15683번: 감시

 

 

 

 

---

2. 설계

---

 

처음에는 쉬운 문제인 줄 알았던 이유가 각 감시카메라에 대해 많은 영역을 커버할 수 있는 방향을 정하고, 커버 영역을 세서 남은 영역에 대한 최소값을 구하고자 했다. 그런데, 이렇게 하면 다른 감시 카메라가 감시했던 영역도 또 감시했다고 체크해서 전체 영역이 20개인데, 감시 영역이 20을 훌쩍 넘어버릴 수 있다.

 

중복 감시되는 부분을 막기 위해 1) 감시 카메라들의 방향 조합을 구하고, 2) 한 카메라가 이미 감시한 부분을 체크해서 중복 감시를 막는다. 3) 해당 조합을 검토했을 때 최소 사각지대 영역을 구한다.

 

 

 

1) 감시카메라 조합 구하기 (DFS)

public static void DFS(int depth) {
	if(depth==CCTVList.size()) {
			
		CopyMap();
			
		for(int i=0;i<CCTVList.size();i++) {
			realDirec(i,selCCTVMethod[i]);//i번째 CCTV가 이 방향으로 갈 것이다.
		}
		result=Math.min(result, CountZeroArea());
		return;
	}
		
	for(int d=0;d<4;d++) {
		selCCTVMethod[depth] = d;
		DFS(depth+1);
	}
}

 

여기서는 각 감시카메라 별 어떤 방향으로 감시할 것인지에 대한 방법을 정한다.

 

1번 카메라는 - 상/하/좌/우 4가지 방법으로 감시할 수 있다.

2번 카메라는 - 상하 / 좌우 2가지 방법으로 감시할 수 있다.

3번 카메라는 - 상우 / 우하 / 하좌 / 좌상 4가지 방법으로 감시할 수 있다.

4번 카메라는 - 좌상우 / 상우하 / 우하좌 / 하좌상 4가지 방법으로 감시할 수 있다.

5번 카메라는 - 상하좌우 1가지  방법으로 감시할 수 있다.

 

조합을 뽑아내기 위해서 고려해야할 것은 2번 카메라이다.

5번 카메라는 고정적으로 1가지 방법 뿐이어서 1,3,4번 카메라가 4가지 방법을 고를 때 영향을 미치진 않는다.

하지만 2번 카메라는 영향을 미친다.

 

1번 카메라, 2번 카메라가 있다고 가정해본다.

 

1번 카메라가 "상" 일 때, 2번 카메라는 "상하"와 "좌우"가 나올 수 있다.

1번 카메라가 "하"일 때 , 2번 카메라는 "상하"와 "좌우"가 나올 수 있다.

 

때문에 2번 카메라는 0번 3번 방법에서는 "상하" 방식으로 감시하고, 1번 4번 방법에서는 "좌우" 방식으로 감시하는 식으로 진행되어야 한다.

 

일단 이렇게 가정해놓고, 각 카메라가 0~3 방법 중 어떤 방법으로 진행할 것인지 조합을 뽑는 것이다.

 

 

 

2) 조합 구하기 완료 (Map을 copy)

지도를 복사하는 이유는 해당 조합에 대한 감시 영역을 체크하기 위함이다.

public static void CopyMap() {
	copyMap = new int[row_count][col_count];
		
	for(int i=0;i<row_count;i++) {
		System.arraycopy(map[i], 0, copyMap[i], 0, col_count);
	}
}

System.arraycopy를 이용해 각 Row 별로 1차원 배열을 복사해줬다.

 

 

 

3) 조합 구하기 완료 (감시 방법에 대한 감시할 방향 설정하기)

public static void realDirec(int n, int method) {
		
	if(CCTVList.get(n).type==1) {
		//상/우/하/좌
		Calculation(n, method); //n번째 CCTV는 이 방향을 감시 
	}else if(CCTVList.get(n).type==2) {
		//상하 / 좌우
		if(method==0 || method==2) {
			//상하 방법 
			Calculation(n, 0);
			Calculation(n, 2);
		}else {
			//좌우 방법 
			Calculation(n, 1);
			Calculation(n, 3);
		}
	}else if(CCTVList.get(n).type==3) {
		//상우 / 우하 / 하좌 / 좌상
		if(method==0) {
			//상우
			Calculation(n, 0);
			Calculation(n, 1);
		}
		else if(method==1) {
			//우하 
			Calculation(n, 1);
			Calculation(n, 2);
		}
		else if(method==2) {
			//하좌 
			Calculation(n, 2);
			Calculation(n, 3);
		}
		else if(method==3) {
			//좌상 
			Calculation(n, 3);
			Calculation(n, 0);
		}
			
	}else if(CCTVList.get(n).type==4) {
		//좌상우 / 상우하 / 우하좌 / 하좌상
		if(method==0) {
			//좌상우
			Calculation(n, 3);
			Calculation(n, 0);
			Calculation(n, 1);
		}
		else if(method==1) {
			//상우하 
			Calculation(n, 0);
			Calculation(n, 1);
			Calculation(n, 2);
		}
		else if(method==2) {
			//우하좌 
			Calculation(n, 1);
			Calculation(n, 2);
			Calculation(n, 3);
		}
		else if(method==3) {
			//하좌상 
			Calculation(n, 2);
			Calculation(n, 3);
			Calculation(n, 0);
		}
			
	}else if(CCTVList.get(n).type==5) {
		//모든방향 
		Calculation(n, 0);
		Calculation(n, 1);
		Calculation(n, 2);
		Calculation(n, 3);
	}
		
}

위에서 했던 말 반복이다.

 

 

1번 카메라는 - 상/하/좌/우 4가지 방법으로 감시할 수 있다.

0번 방법 : 상

1번 방법 : 우

2번 방법 : 하

3번 방법 : 좌

 

 

2번 카메라는 - 상하 / 좌우 2가지 방법으로 감시할 수 있다. (주의)

0번 방법 : 상하

1번 방법 : 좌우

2번 방법 : 상하

3번 방법 : 좌우

 

 

3번 카메라는 - 상우 / 우하 / 하좌 / 좌상 4가지 방법으로 감시할 수 있다.

0번 방법 : 상우

1번 방법 : 우하

2번 방법 : 하좌

3번 방법 : 좌상

 

 

4번 카메라는 - 좌상우 / 상우하 / 우하좌 / 하좌상 4가지 방법으로 감시할 수 있다.

0번 방법 : 좌상우

1번 방법 : 상우하

2번 방법 : 우하좌

3번 방법 : 하좌상

 

 

5번 카메라는 - 상하좌우 1가지  방법으로 감시할 수 있다. (고정)

0번 방법 : 상하좌우

1번 방법 : 상하좌우

2번 방법 : 상하좌우

3번 방법 : 상하좌우

 

 

 

4) 감시 영역 체크

public static void Calculation(int n, int direc) {
		
	CCTV curCCTV = CCTVList.get(n);
	int newR = curCCTV.row;
	int newC = curCCTV.col;
		
	while(true) {
		newR += drc[direc][0];
		newC += drc[direc][1];
			
		//범위 체크
		if(newR<0||newR>=row_count||newC<0||newC>=col_count) break;
			
		//벽인지
		if(copyMap[newR][newC]==6) break;
			
		//CCTV인지 
		if(copyMap[newR][newC]>=1 && copyMap[newR][newC]<=5) continue;
			
		//빈공간인지 
		copyMap[newR][newC] = -1;
			
			
	}
		
}

realDirec 함수에서 보내 온 4방 중 하나로 복사한 지도에 감시 영역을 -1로 체크한다.

 

 

 

5) 사각지대 (0인 곳) 계산

public static int CountZeroArea() {
	int count = 0;
		
	for(int i=0;i<row_count;i++) {
		for(int j=0;j<col_count;j++) {
			if(copyMap[i][j]==0) {
				count++;
			}
		}
	}
	return count;
}

여기서 나온 계산은 DFS 함수로 최종적으로 보내지는데, DFS 함수에서 전역 변수로 선언된 result 변수에 최소 영역 갯수를 비교해서 넣어주고, 최종 최소 영역을 출력해주면 된다.

 

 

---

3. 전체코드

---

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
static ArrayList<CCTV> CCTVList = new ArrayList<>();
	
	static int row_count;
	static int col_count;
	static int[][] map, copyMap;
	
	//type check
	static int[][] drc = {{-1,0},{0,1},{1,0},{0,-1}}; //상 우 하 좌 
	
	static int[] selCCTVMethod;
	
	static int result = 54321;
	
	static class CCTV{
		int row;
		int col;
		int type; //1~5
		
		
		public CCTV(int row, int col, int type) {
			super();
			this.row = row;
			this.col = col;
			this.type = type;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		row_count = sc.nextInt();//세로
		col_count = sc.nextInt();//가로 
		
		map = new int[row_count][col_count];
		
		//map에 데이터 입력받을 때 cctv 위치 체크 (1~5)
		for(int i=0;i<row_count;i++) {
			for(int j=0;j<col_count;j++) {
				map[i][j] = sc.nextInt();
						
				//CCTV 추가 
				if(map[i][j]>=1 && map[i][j]<=5) {
					CCTVList.add(new CCTV(i,j,map[i][j]));
				}
			}
		}
				
		//입력 끝 
		
		selCCTVMethod = new int[CCTVList.size()];
		
		//연산시작 
		DFS(0);
		
		System.out.println(result);
		
		
	}
	
	public static void DFS(int depth) {
		if(depth==CCTVList.size()) {
			
			CopyMap();
			
			for(int i=0;i<CCTVList.size();i++) {
				realDirec(i,selCCTVMethod[i]);//i번째 CCTV가 이 방향으로 갈 것이다.
			}
			result=Math.min(result, CountZeroArea());
			return;
		}
		
		for(int d=0;d<4;d++) {
			selCCTVMethod[depth] = d;
			DFS(depth+1);
		}
	}
	
	public static void realDirec(int n, int method) {
		
		if(CCTVList.get(n).type==1) {
			//상/우/하/좌
			Calculation(n, method); //n번째 CCTV는 이 방향을 감시 
		}else if(CCTVList.get(n).type==2) {
			//상하 / 좌우
			if(method==0 || method==2) {
				//상하 방법 
				Calculation(n, 0);
				Calculation(n, 2);
			}else {
				//좌우 방법 
				Calculation(n, 1);
				Calculation(n, 3);
			}
		}else if(CCTVList.get(n).type==3) {
			//상우 / 우하 / 하좌 / 좌상
			if(method==0) {
				//상우
				Calculation(n, 0);
				Calculation(n, 1);
			}
			else if(method==1) {
				//우하 
				Calculation(n, 1);
				Calculation(n, 2);
			}
			else if(method==2) {
				//하좌 
				Calculation(n, 2);
				Calculation(n, 3);
			}
			else if(method==3) {
				//좌상 
				Calculation(n, 3);
				Calculation(n, 0);
			}
			
		}else if(CCTVList.get(n).type==4) {
			//좌상우 / 상우하 / 우하좌 / 하좌상
			if(method==0) {
				//좌상우
				Calculation(n, 3);
				Calculation(n, 0);
				Calculation(n, 1);
			}
			else if(method==1) {
				//상우하 
				Calculation(n, 0);
				Calculation(n, 1);
				Calculation(n, 2);
			}
			else if(method==2) {
				//우하좌 
				Calculation(n, 1);
				Calculation(n, 2);
				Calculation(n, 3);
			}
			else if(method==3) {
				//하좌상 
				Calculation(n, 2);
				Calculation(n, 3);
				Calculation(n, 0);
			}
			
		}else if(CCTVList.get(n).type==5) {
			//모든방향 
			Calculation(n, 0);
			Calculation(n, 1);
			Calculation(n, 2);
			Calculation(n, 3);
		}
		
	}
	
	public static void Calculation(int n, int direc) {
		
		CCTV curCCTV = CCTVList.get(n);
		int newR = curCCTV.row;
		int newC = curCCTV.col;
		
		while(true) {
			newR += drc[direc][0];
			newC += drc[direc][1];
			
			//범위 체크
			if(newR<0||newR>=row_count||newC<0||newC>=col_count) break;
			
			//벽인지
			if(copyMap[newR][newC]==6) break;
			
			//CCTV인지 
			if(copyMap[newR][newC]>=1 && copyMap[newR][newC]<=5) continue;
			
			//빈공간인지 
			copyMap[newR][newC] = -1;
			
			
		}
		
	}
	
	public static void CopyMap() {
		copyMap = new int[row_count][col_count];
		
		for(int i=0;i<row_count;i++) {
			System.arraycopy(map[i], 0, copyMap[i], 0, col_count);
		}
	}
	
	public static int CountZeroArea() {
		int count = 0;
		
		for(int i=0;i<row_count;i++) {
			for(int j=0;j<col_count;j++) {
				if(copyMap[i][j]==0) {
					count++;
				}
			}
		}
		return count;
	}
}

 

---

나한테는 이 문제는 어렵다고 생각되었다.

언제쯤이면 가뿐하게 풀 수 있을까 : )