[백준] 15683 - 감시 (JAVA)

1. 소요시간 : 1시간
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 4
4. 문제 유형 : 구현, 브루트포스 알고리즘, 시뮬레이션
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/15683
8. 푼 날짜 : 2023.04.08

1. 사용한 자료구조 & 알고리즘

백트래킹. 큐. 시뮬레이션. 구현. 브루트포스 알고리즘

2. 사고과정

그리디 알고리즘은 아닐 것이라고 생각, N과 M이 작고, CCTV 의 개수도 최대 8개이므로 백트래킹으로 풀 수 있을 것으로 생각했음.
결국 모든 경우의 수를 다 따져봐야 함.

그 과정에서 위와 같은 경우의 수가 나올 수 있음.

3. 풀이과정

1. 현재 위치가 CCTV면 위치와, 어떤 종류의 CCTV인지 list에 저장
2. 백트래킹 탐색.
3. 몇번 CCTV냐에 따라서 list 에서 방향 값과 좌표를 추가해서 dfs로 이어서 탐색
4. depth 가 CCTV의 개수만큼 왔다면, 이제 queue를 통해서 벽을 만나기 전까지 탐색했다는 표시를 함. 탐색한 곳은 7로 표시.
5. queue가 비었다면 모든 탐색을 완료한 것. 이제 맵에있는 0의 개수를 세어줌.
6. 세어줄 때마다 최솟값을 갱신

4. 소스코드

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

public class Main{
	static int map[][];

	static int arr1[][]= {{1},{2},{3},{4}};
	static int arr2[][]= {{2,4},{1,3}};
	static int arr3[][]= {{1,2},{2,3},{3,4},{4,1}};
	static int arr4[][]= {{4,1,2},{1,2,3},{2,3,4},{3,4,1}};
	static int arr5[][]= {{1,2,3,4}};
	static int min=Integer.MAX_VALUE;

	static ArrayList<Integer[]> list=new ArrayList<>();

	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st;

		ArrayList<Integer[]> arr = new ArrayList<>();


		st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		map=new int[N][M];

		for(int i=0;i<N;i++) {
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<M;j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
				if(map[i][j]>=1&&map[i][j]<=5)
					list.add(new Integer[] {i,j,map[i][j]});
			}
		}
		
		backtracking(0,arr);
		
		System.out.println(min);




	}
	public static void backtracking(int depth,ArrayList<Integer[]> array) {
		if(depth==list.size()) {
			checkingCCTV(array);
			return ;
		}

		int y=list.get(depth)[0];
		int x=list.get(depth)[1];
		int number= list.get(depth)[2];
		switch(number) {
		case 1:
			for(int i=0;i<arr1.length;i++) {
				ArrayList<Integer[]> temp=new ArrayList<>(array);
				for(int j=0;j<arr1[0].length;j++) {
					temp.add(new Integer[] {y,x,arr1[i][j]});
				}
				backtracking(depth+1,temp);
			}
			break;

		case 2: 
			for(int i=0;i<arr2.length;i++) {
				ArrayList<Integer[]> temp=new ArrayList<>(array);
				for(int j=0;j<arr2[0].length;j++) {
					temp.add(new Integer[] {y,x,arr2[i][j]});
				}
				backtracking(depth+1,temp);
			}
			break;

		case 3:
			for(int i=0;i<arr3.length;i++) {
				ArrayList<Integer[]> temp=new ArrayList<>(array);
				for(int j=0;j<arr3[0].length;j++) {
					temp.add(new Integer[] {y,x,arr3[i][j]});
				}
				backtracking(depth+1,temp);
			}
			break;

		case 4:
			for(int i=0;i<arr4.length;i++) {
				ArrayList<Integer[]> temp=new ArrayList<>(array);
				for(int j=0;j<arr4[0].length;j++) {
					temp.add(new Integer[] {y,x,arr4[i][j]});
				}
				backtracking(depth+1,temp);
			}
			break;

		case 5:
			for(int i=0;i<arr5.length;i++) {
				ArrayList<Integer[]> temp=new ArrayList<>(array);
				for(int j=0;j<arr5[0].length;j++) {
					temp.add(new Integer[] {y,x,arr5[i][j]});
				}
				backtracking(depth+1,temp);
			}
			break;

		}
	}

	public static void checkingCCTV(ArrayList<Integer[]> array) {
		int copy[][]=new int[map.length][map[0].length];
		for(int i=0;i<copy.length;i++)
			copy[i]=map[i].clone();
		
		Queue<Integer[]> queue=new LinkedList<>();
		for(int i=0;i<array.size();i++) {
			Integer temp[]= array.get(i);
			int y=temp[0];
			int x=temp[1];
			int dir=temp[2];
			queue.add(new Integer[] {y,x,dir});
		}
		
		//1은 위쪽, 2는 오른쪽, 3은 아래쪽, 4는 왼쪽
		while(!queue.isEmpty()) {
			Integer temp[]=queue.poll();
			int y=temp[0];
			int x=temp[1];
			int dir=temp[2];
			fillMap(y,x,dir,copy);
		}
		
		countMap(copy);
		
		
		
		
	}
	public static void fillMap(int y,int x,int dir,int copy[][]) {
		int dy[]= {0,-1,0,1,0};
		int dx[]= {0,0,1,0,-1};
		while(true) {
			y+=dy[dir];
			x+=dx[dir];
			if(y<0||x<0||y>=copy.length||x>=copy[0].length)
				break;
			if(copy[y][x]==6)
				break;
			
			if(copy[y][x]>=1&&copy[y][x]<=5) continue;
			
			copy[y][x]=7;
			
		}
		
	}
	public static void countMap(int copy[][]) {
		int count = 0;
		for(int i=0;i<copy.length;i++) {
			for(int j=0;j<copy[0].length;j++) {
				if(copy[i][j]==0) count++;
			
			}

	
		}
	
		min=Math.min(count,min);
		
	}

}

5. 결과

6. 회고

이번 문제는 큰 어려움 없이 1트만에 통과 ..!
지금까지 문제 푸는데에 있어서 문제는 결국 풀지만, 시간이 오래 걸리는 것에 대해서 상당히 신경 쓰는 중이다.

걸리는 시간을 줄여보도록 하자. (사실 문제 푸는 중에도 100% 집중해서 푼다기 보다는 잡생각도 좀 많이 해가지고 오래 걸리는 것 같다.. )
하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212