백준 알고리즘 - 감시
CCTV의 종류는 총 5개지만
종류마다 방향의 개수가 정해져있지만,
모두 4방향의 경우가 있다고 가정하고 문제를 접근했다.
물론 5번카메라 같은 경우는 방향이 1가지 이기 때문에 이 요소를 고려하고 짠다면,
불필요한 연산을 하지 않아도 된다.
CCTV의 개수는 8개를 넘지 않는다고 하였다.
이 말은 4의 8제곱의 경우의 수를 넘지 않는다.
DFS를 통해 탐색 후 CCTV가 감시하는 부분을 7로 채운 후
마지막의 0의 개수를 세어서 HashSet에 다가 넣어주었다.
그리고 다시 7로 채운 부분을 0으로 돌려주었다.
이 과정을 모든 경우의 수 만큼 반복했다.
모든 경우의 수를 검사하고 난 후 최소값을 출력해 주도록 짰다.
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
public class Main {
private static class CCTV{
int x;
int y;
int type;
boolean visited[];
public CCTV(int x, int y, int type) {
this.x = x;
this.y = y;
this.type = type;
this.visited = new boolean[4];
}
}
private static int[] resultDirections;
private static int[][] room;
private static int directions = 4;
private static int cctvCnt = 0;//cctv 개수
private static ArrayList<CCTV> allCCTV = new ArrayList<>();
private static HashSet<Integer> resultZero = new HashSet<>();
private static int height;
private static int width;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
height = sc.nextInt();
width = sc.nextInt();
room = new int[height][width];
for(int i=0; i<height; i++) {
for(int j=0; j<width; j++) {
room[i][j] = sc.nextInt();
if(room[i][j] == 0 || room[i][j] == 6)
continue;
allCCTV.add(new CCTV(i, j, room[i][j]));
}
}
cctvCnt = allCCTV.size();
resultDirections = new int[cctvCnt];
DFS();
System.out.println(minZeroCnt(resultZero));
}
private static void DFS(){
if (cctvCnt > 0) {
for (int i = 0; i < directions; i++) {
CCTV cctv = allCCTV.get(0);
cctv.visited[i] = true;
DFS_recursion(0, i);
}
} else {
int zeroCnt = printRoomAndCountZero(room);
resultZero.add(zeroCnt);
}
}
private static void DFS_recursion(int depth, int direction){
resultDirections[depth] = direction;
if (depth == cctvCnt-1) {
for (int i = 0; i < resultDirections.length; i++){
CCTV cctv = allCCTV.get(i);
mark7(cctv.type, resultDirections[i], cctv.x, cctv.y);
}
int zeroCnt = printRoomAndCountZero(room);
resultZero.add(zeroCnt);
getBack7to0(room);
} else {
for (int i = 0; i < directions; i++){
CCTV cctv = allCCTV.get(depth + 1);
if (cctv.visited[i])
continue;
cctv.visited[i] = true;
DFS_recursion(depth + 1, i);
cctv.visited[i] = false;
}
}
}
private static int minZeroCnt(HashSet<Integer> set){
int minVal = 100;
Iterator iterator = set.iterator();
while(iterator.hasNext()){
int val = (Integer)iterator.next();
if(val < minVal)
minVal = val;
}
return minVal;
}
private static int printRoomAndCountZero(int[][] arr){
int cnt = 0;
for (int i = 0; i < arr.length; i++){
for (int j = 0; j < arr[i].length; j++){
if (arr[i][j] == 0)
cnt++;
}
}
return cnt;
}
private static void getBack7to0(int[][] arr){
for (int i = 0; i < arr.length; i++){
for (int j = 0; j < arr[i].length; j++){
if (arr[i][j] == 7)
arr[i][j] = 0;
}
}
}
private static void mark7(int cctvType, int direction, int x, int y){
switch (cctvType) {
case 1:
switch (direction) {
case 0://up
mark7Up(x,y);
break;
case 1://right
mark7Right(x,y);
break;
case 2://down
mark7Down(x,y);
break;
case 3://left
mark7Left(x,y);
break;
}
break;
case 2:
switch (direction) {
case 0://up
mark7Up(x,y);
mark7Down(x,y);
break;
case 1://right
mark7Left(x,y);
mark7Right(x,y);
break;
case 2://down
mark7Up(x,y);
mark7Down(x,y);
break;
case 3://left
mark7Left(x,y);
mark7Right(x,y);
break;
}
break;
case 3:
switch (direction) {
case 0://up
mark7Up(x,y);
mark7Right(x,y);
break;
case 1://right
mark7Right(x,y);
mark7Down(x,y);
break;
case 2://down
mark7Down(x,y);
mark7Left(x,y);
break;
case 3://left
mark7Left(x,y);
mark7Up(x,y);
break;
}
break;
case 4:
switch (direction) {
case 0://up
mark7Left(x,y);
mark7Up(x,y);
mark7Right(x,y);
break;
case 1://right
mark7Up(x,y);
mark7Right(x,y);
mark7Down(x,y);
break;
case 2://down
mark7Right(x,y);
mark7Down(x,y);
mark7Left(x,y);
break;
case 3://left
mark7Down(x,y);
mark7Left(x,y);
mark7Up(x,y);
break;
}
break;
case 5:
switch (direction) {
case 0://up
mark7Up(x,y);
mark7Right(x,y);
mark7Left(x,y);
mark7Down(x,y);
break;
case 1://right
mark7Up(x,y);
mark7Right(x,y);
mark7Left(x,y);
mark7Down(x,y);
break;
case 2://down
mark7Up(x,y);
mark7Right(x,y);
mark7Left(x,y);
mark7Down(x,y);
break;
case 3://left
mark7Up(x,y);
mark7Right(x,y);
mark7Left(x,y);
mark7Down(x,y);
break;
}
break;
}
}
private static void mark7Up(int x, int y) {
for (int i = x-1; i > -1; i--){
if(room[i][y] == 6)
break;
if(room[i][y] == 1 || room[i][y] == 2 || room[i][y] == 3 || room[i][y] == 4 || room[i][y] == 5)
continue;
room[i][y] = 7;
}
}
private static void mark7Right(int x, int y) {
for (int i = y+1; i < room[x].length; i++){
if(room[x][i] == 6)
break;
if(room[x][i] == 1 || room[x][i] == 2 || room[x][i] == 3 || room[x][i] == 4 || room[x][i] == 5)
continue;
room[x][i] = 7;
}
}
private static void mark7Down(int x, int y) {
for (int i = x+1; i < room.length; i++){
if(room[i][y] == 6)
break;
if(room[i][y] == 1 || room[i][y] == 2 || room[i][y] == 3 || room[i][y] == 4 || room[i][y] == 5)
continue;
room[i][y] = 7;
}
}
private static void mark7Left(int x, int y) {
for (int i = y-1; i > -1; i--){
if(room[x][i] == 6)
break;
if(room[x][i] == 1 || room[x][i] == 2 || room[x][i] == 3 || room[x][i] == 4 || room[x][i] == 5)
continue;
room[x][i] = 7;
}
}
}
종류마다 방향의 개수가 정해져있지만,
모두 4방향의 경우가 있다고 가정하고 문제를 접근했다.
물론 5번카메라 같은 경우는 방향이 1가지 이기 때문에 이 요소를 고려하고 짠다면,
불필요한 연산을 하지 않아도 된다.
CCTV의 개수는 8개를 넘지 않는다고 하였다.
이 말은 4의 8제곱의 경우의 수를 넘지 않는다.
DFS를 통해 탐색 후 CCTV가 감시하는 부분을 7로 채운 후
마지막의 0의 개수를 세어서 HashSet에 다가 넣어주었다.
그리고 다시 7로 채운 부분을 0으로 돌려주었다.
이 과정을 모든 경우의 수 만큼 반복했다.
모든 경우의 수를 검사하고 난 후 최소값을 출력해 주도록 짰다.
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
public class Main {
private static class CCTV{
int x;
int y;
int type;
boolean visited[];
public CCTV(int x, int y, int type) {
this.x = x;
this.y = y;
this.type = type;
this.visited = new boolean[4];
}
}
private static int[] resultDirections;
private static int[][] room;
private static int directions = 4;
private static int cctvCnt = 0;//cctv 개수
private static ArrayList<CCTV> allCCTV = new ArrayList<>();
private static HashSet<Integer> resultZero = new HashSet<>();
private static int height;
private static int width;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
height = sc.nextInt();
width = sc.nextInt();
room = new int[height][width];
for(int i=0; i<height; i++) {
for(int j=0; j<width; j++) {
room[i][j] = sc.nextInt();
if(room[i][j] == 0 || room[i][j] == 6)
continue;
allCCTV.add(new CCTV(i, j, room[i][j]));
}
}
cctvCnt = allCCTV.size();
resultDirections = new int[cctvCnt];
DFS();
System.out.println(minZeroCnt(resultZero));
}
private static void DFS(){
if (cctvCnt > 0) {
for (int i = 0; i < directions; i++) {
CCTV cctv = allCCTV.get(0);
cctv.visited[i] = true;
DFS_recursion(0, i);
}
} else {
int zeroCnt = printRoomAndCountZero(room);
resultZero.add(zeroCnt);
}
}
private static void DFS_recursion(int depth, int direction){
resultDirections[depth] = direction;
if (depth == cctvCnt-1) {
for (int i = 0; i < resultDirections.length; i++){
CCTV cctv = allCCTV.get(i);
mark7(cctv.type, resultDirections[i], cctv.x, cctv.y);
}
int zeroCnt = printRoomAndCountZero(room);
resultZero.add(zeroCnt);
getBack7to0(room);
} else {
for (int i = 0; i < directions; i++){
CCTV cctv = allCCTV.get(depth + 1);
if (cctv.visited[i])
continue;
cctv.visited[i] = true;
DFS_recursion(depth + 1, i);
cctv.visited[i] = false;
}
}
}
private static int minZeroCnt(HashSet<Integer> set){
int minVal = 100;
Iterator iterator = set.iterator();
while(iterator.hasNext()){
int val = (Integer)iterator.next();
if(val < minVal)
minVal = val;
}
return minVal;
}
private static int printRoomAndCountZero(int[][] arr){
int cnt = 0;
for (int i = 0; i < arr.length; i++){
for (int j = 0; j < arr[i].length; j++){
if (arr[i][j] == 0)
cnt++;
}
}
return cnt;
}
private static void getBack7to0(int[][] arr){
for (int i = 0; i < arr.length; i++){
for (int j = 0; j < arr[i].length; j++){
if (arr[i][j] == 7)
arr[i][j] = 0;
}
}
}
private static void mark7(int cctvType, int direction, int x, int y){
switch (cctvType) {
case 1:
switch (direction) {
case 0://up
mark7Up(x,y);
break;
case 1://right
mark7Right(x,y);
break;
case 2://down
mark7Down(x,y);
break;
case 3://left
mark7Left(x,y);
break;
}
break;
case 2:
switch (direction) {
case 0://up
mark7Up(x,y);
mark7Down(x,y);
break;
case 1://right
mark7Left(x,y);
mark7Right(x,y);
break;
case 2://down
mark7Up(x,y);
mark7Down(x,y);
break;
case 3://left
mark7Left(x,y);
mark7Right(x,y);
break;
}
break;
case 3:
switch (direction) {
case 0://up
mark7Up(x,y);
mark7Right(x,y);
break;
case 1://right
mark7Right(x,y);
mark7Down(x,y);
break;
case 2://down
mark7Down(x,y);
mark7Left(x,y);
break;
case 3://left
mark7Left(x,y);
mark7Up(x,y);
break;
}
break;
case 4:
switch (direction) {
case 0://up
mark7Left(x,y);
mark7Up(x,y);
mark7Right(x,y);
break;
case 1://right
mark7Up(x,y);
mark7Right(x,y);
mark7Down(x,y);
break;
case 2://down
mark7Right(x,y);
mark7Down(x,y);
mark7Left(x,y);
break;
case 3://left
mark7Down(x,y);
mark7Left(x,y);
mark7Up(x,y);
break;
}
break;
case 5:
switch (direction) {
case 0://up
mark7Up(x,y);
mark7Right(x,y);
mark7Left(x,y);
mark7Down(x,y);
break;
case 1://right
mark7Up(x,y);
mark7Right(x,y);
mark7Left(x,y);
mark7Down(x,y);
break;
case 2://down
mark7Up(x,y);
mark7Right(x,y);
mark7Left(x,y);
mark7Down(x,y);
break;
case 3://left
mark7Up(x,y);
mark7Right(x,y);
mark7Left(x,y);
mark7Down(x,y);
break;
}
break;
}
}
private static void mark7Up(int x, int y) {
for (int i = x-1; i > -1; i--){
if(room[i][y] == 6)
break;
if(room[i][y] == 1 || room[i][y] == 2 || room[i][y] == 3 || room[i][y] == 4 || room[i][y] == 5)
continue;
room[i][y] = 7;
}
}
private static void mark7Right(int x, int y) {
for (int i = y+1; i < room[x].length; i++){
if(room[x][i] == 6)
break;
if(room[x][i] == 1 || room[x][i] == 2 || room[x][i] == 3 || room[x][i] == 4 || room[x][i] == 5)
continue;
room[x][i] = 7;
}
}
private static void mark7Down(int x, int y) {
for (int i = x+1; i < room.length; i++){
if(room[i][y] == 6)
break;
if(room[i][y] == 1 || room[i][y] == 2 || room[i][y] == 3 || room[i][y] == 4 || room[i][y] == 5)
continue;
room[i][y] = 7;
}
}
private static void mark7Left(int x, int y) {
for (int i = y-1; i > -1; i--){
if(room[x][i] == 6)
break;
if(room[x][i] == 1 || room[x][i] == 2 || room[x][i] == 3 || room[x][i] == 4 || room[x][i] == 5)
continue;
room[x][i] = 7;
}
}
}
댓글
댓글 쓰기