본문 바로가기
Algorithm/문제 풀이

[알고리즘] 감시 (백준 15683번)

by Sky Titan 2020. 9. 19.
728x90
 

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감��

www.acmicpc.net

 브루트 포스 + 시뮬레이션 문제다. 감시 카메라의 유형과 유형마다 감시할 수 있는 방향의 경우의 수가 많기 때문에 모듈화를 잘 해야한다.

 

Solution

 위의 경우에서 1번에서 5번 카메라까지 각각 4, 2, 4, 4, 1가지의 경우의 수가 나온다. 이 경우의 수를 배열에 저장해놓는다.

static int cases[] = {0, 4, 2, 4, 4, 1};

 

 또한 각 카메라의 위치를 ArrayList에 보관한다.

		for(int i = 0;i < N;i++)
		{
			list = br.readLine().split(" ");

			for(int j = 0;j < M;j++)
			{
				map[i][j] = Integer.parseInt(list[j]);
				if(0 < map[i][j] && map[i][j] < 6)
					cameras.add(new Position(i, j));
			}
		}

 모듈은 크게 4가지로 구성했다.

 

1. findAllCases

 브루트 포스 탐색을 하는 재귀함수이다. 현재 존재하는 카메라들의 모든 가능한 경우의 수를 다 조합해본 후 사각지대가 최소가 되는 경우를 구한다.

	static void findAllCases(int camera, int N, int M)
	{
		if(camera == cameras.size())
		{
			int count = 0;

			for(int i = 0;i < N;i++)
			{
				for(int j = 0;j < M;j++)
				{
					if(map[i][j] == 0)
						count++;
				}
			}
			min = Math.min(min, count);
		}
		else
		{
			int camera_number = map[cameras.get(camera).x][cameras.get(camera).y];
			Stack<Position> recover_stack = new Stack<>();

			for(int i = 0;i < cases[camera_number];i++)
			{
				makeMap(cameras.get(camera).x, cameras.get(camera).y, i, camera_number, recover_stack);

				findAllCases(camera + 1, N, M);

				recoverMap(recover_stack);
			}
		}
	}

 

2. makeMap

 카메라 유형과 방향에 따라서 감시 영역을 지정한다.

//카메라 타입에 따라서 감시영역 지정
	static void makeMap(int x, int y, int index, int camera_number, Stack<Position> recover_stack)
	{
		//1번 카메라
		if(camera_number == 1)
		{
			setObservation(x, y, index, recover_stack);
		}
		else if(camera_number == 2)
		{
			//남북
			if(index == 0)
			{
				setObservation(x, y, 2, recover_stack);
				setObservation(x, y, 3, recover_stack);
			}
			//동서
			else
			{
				setObservation(x, y, 0, recover_stack);
				setObservation(x, y, 1, recover_stack);
			}
		}
		else if(camera_number == 3)
		{
			//북동
			if(index == 0)
			{
				setObservation(x, y, 3, recover_stack);
				setObservation(x, y, 0, recover_stack);
			}
			//동남
			else if(index == 1)
			{
				setObservation(x, y, 0, recover_stack);
				setObservation(x, y, 2, recover_stack);
			}
			//남서
			else if(index == 2)
			{
				setObservation(x, y, 2, recover_stack);
				setObservation(x, y, 1, recover_stack);
			}
			//서북
			else
			{
				setObservation(x, y, 1, recover_stack);
				setObservation(x, y, 3, recover_stack);
			}
		}
		else if(camera_number == 4)
		{
			//서북동
			if(index == 0)
			{
				setObservation(x, y, 1, recover_stack);
				setObservation(x, y, 3, recover_stack);
				setObservation(x, y, 0, recover_stack);
			}
			//북동남
			else if(index == 1)
			{
				setObservation(x, y, 3, recover_stack);
				setObservation(x, y, 0, recover_stack);
				setObservation(x, y, 2, recover_stack);
			}
			//동남서
			else if(index == 2)
			{
				setObservation(x, y, 0, recover_stack);
				setObservation(x, y, 2, recover_stack);
				setObservation(x, y, 1, recover_stack);
			}
			//남서북
			else
			{
				setObservation(x, y, 2, recover_stack);
				setObservation(x, y, 1, recover_stack);
				setObservation(x, y, 3, recover_stack);
			}
		}
		else
		{
			for(int i = 0;i < 4;i++)
				setObservation(x, y, i, recover_stack);
		}
	}

 

3. setObservation

현재 카메라 위치를 기준으로 동서남북 4방향으로 감시 영역을 지정한다.

//감시 영역 지정
	public static void setObservation(int x, int y, int index, Stack<Position> recover_stack)
	{
		//동
		if(index == 0)
		{
			for(int j = y + 1;j < map[x].length;j++)
			{
				//감시영역 지정
				if(map[x][j] == 0)
				{
					map[x][j] = -1;
					recover_stack.push(new Position(x, j));
				}
				//벽이면 멈춤
				else if(map[x][j] == 6)
					break;
			}
		}
		//서
		else if(index == 1)
		{
			for(int j = y - 1;j >= 0;j--)
			{
				//감시영역 지정
				if(map[x][j] == 0)
				{
					map[x][j] = -1;
					recover_stack.push(new Position(x, j));
				}
				else if(map[x][j] == 6)
					break;
			}
		}
		//남
		else if(index == 2)
		{
			for(int i = x + 1;i < map.length;i++)
			{
				//감시영역 지정
				if(map[i][y] == 0)
				{
					map[i][y] = -1;
					recover_stack.push(new Position(i, y));
				}
				else if(map[i][y] == 6)
					break;
			}
		}
		//북
		else
		{
			for(int i = x - 1;i >= 0;i--)
			{
				//감시영역 지정
				if(map[i][y] == 0)
				{
					map[i][y] = -1;
					recover_stack.push(new Position(i, y));
				}
				else if(map[i][y] == 6)
					break;
			}
		}
	}

 

4. recoverMap

 해당 카메라 유형의 감시영역 지정하고 재귀 탐색이 끝나면 감시영역으로 지정되었던 recoverStack에 들어가있는 위치들의 영역들을 다시 원래대로 복구시킨다.

//원래대로 복구
	public static void recoverMap(Stack<Position> recover_stack)
	{
		while(!recover_stack.isEmpty())
		{
			Position p = recover_stack.pop();
			map[p.x][p.y] = 0;
		}
	}

 

 

아래는 전체코드이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

	static int map[][];

	static int cases[] = {0, 4, 2, 4, 4, 1};
	static ArrayList<Position> cameras = new ArrayList<>();
	static int min = Integer.MAX_VALUE;

	public static void solution() throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String[] list = br.readLine().split(" ");

		int N = Integer.parseInt(list[0]);
		int M = Integer.parseInt(list[1]);

		map = new int[N][M];

		for(int i = 0;i < N;i++)
		{
			list = br.readLine().split(" ");

			for(int j = 0;j < M;j++)
			{
				map[i][j] = Integer.parseInt(list[j]);
				if(0 < map[i][j] && map[i][j] < 6)
					cameras.add(new Position(i, j));
			}
		}
		findAllCases(0, N, M);

		if(min == Integer.MAX_VALUE)
			bw.write("0");
		else
			bw.write(min+"");
		bw.close();
		br.close();
	}

	static void findAllCases(int camera, int N, int M)
	{
		if(camera == cameras.size())
		{
			int count = 0;

			for(int i = 0;i < N;i++)
			{
				for(int j = 0;j < M;j++)
				{
					if(map[i][j] == 0)
						count++;
				}
			}
			min = Math.min(min, count);
		}
		else
		{
			int camera_number = map[cameras.get(camera).x][cameras.get(camera).y];
			Stack<Position> recover_stack = new Stack<>();

			for(int i = 0;i < cases[camera_number];i++)
			{
				makeMap(cameras.get(camera).x, cameras.get(camera).y, i, camera_number, recover_stack);

				findAllCases(camera + 1, N, M);

				recoverMap(recover_stack);
			}
		}
	}

	//카메라 타입에 따라서 감시영역 지정
	static void makeMap(int x, int y, int index, int camera_number, Stack<Position> recover_stack)
	{
		//1번 카메라
		if(camera_number == 1)
		{
			setObservation(x, y, index, recover_stack);
		}
		else if(camera_number == 2)
		{
			//남북
			if(index == 0)
			{
				setObservation(x, y, 2, recover_stack);
				setObservation(x, y, 3, recover_stack);
			}
			//동서
			else
			{
				setObservation(x, y, 0, recover_stack);
				setObservation(x, y, 1, recover_stack);
			}
		}
		else if(camera_number == 3)
		{
			//북동
			if(index == 0)
			{
				setObservation(x, y, 3, recover_stack);
				setObservation(x, y, 0, recover_stack);
			}
			//동남
			else if(index == 1)
			{
				setObservation(x, y, 0, recover_stack);
				setObservation(x, y, 2, recover_stack);
			}
			//남서
			else if(index == 2)
			{
				setObservation(x, y, 2, recover_stack);
				setObservation(x, y, 1, recover_stack);
			}
			//서북
			else
			{
				setObservation(x, y, 1, recover_stack);
				setObservation(x, y, 3, recover_stack);
			}
		}
		else if(camera_number == 4)
		{
			//서북동
			if(index == 0)
			{
				setObservation(x, y, 1, recover_stack);
				setObservation(x, y, 3, recover_stack);
				setObservation(x, y, 0, recover_stack);
			}
			//북동남
			else if(index == 1)
			{
				setObservation(x, y, 3, recover_stack);
				setObservation(x, y, 0, recover_stack);
				setObservation(x, y, 2, recover_stack);
			}
			//동남서
			else if(index == 2)
			{
				setObservation(x, y, 0, recover_stack);
				setObservation(x, y, 2, recover_stack);
				setObservation(x, y, 1, recover_stack);
			}
			//남서북
			else
			{
				setObservation(x, y, 2, recover_stack);
				setObservation(x, y, 1, recover_stack);
				setObservation(x, y, 3, recover_stack);
			}
		}
		else
		{
			for(int i = 0;i < 4;i++)
				setObservation(x, y, i, recover_stack);
		}
	}

	//원래대로 복구
	public static void recoverMap(Stack<Position> recover_stack)
	{
		while(!recover_stack.isEmpty())
		{
			Position p = recover_stack.pop();
			map[p.x][p.y] = 0;
		}
	}

	//감시 영역 지정
	public static void setObservation(int x, int y, int index, Stack<Position> recover_stack)
	{
		//동
		if(index == 0)
		{
			for(int j = y + 1;j < map[x].length;j++)
			{
				//감시영역 지정
				if(map[x][j] == 0)
				{
					map[x][j] = -1;
					recover_stack.push(new Position(x, j));
				}
				//벽이면 멈춤
				else if(map[x][j] == 6)
					break;
			}
		}
		//서
		else if(index == 1)
		{
			for(int j = y - 1;j >= 0;j--)
			{
				//감시영역 지정
				if(map[x][j] == 0)
				{
					map[x][j] = -1;
					recover_stack.push(new Position(x, j));
				}
				else if(map[x][j] == 6)
					break;
			}
		}
		//남
		else if(index == 2)
		{
			for(int i = x + 1;i < map.length;i++)
			{
				//감시영역 지정
				if(map[i][y] == 0)
				{
					map[i][y] = -1;
					recover_stack.push(new Position(i, y));
				}
				else if(map[i][y] == 6)
					break;
			}
		}
		//북
		else
		{
			for(int i = x - 1;i >= 0;i--)
			{
				//감시영역 지정
				if(map[i][y] == 0)
				{
					map[i][y] = -1;
					recover_stack.push(new Position(i, y));
				}
				else if(map[i][y] == 6)
					break;
			}
		}
	}

	static class Position{
		int x, y;

		public Position(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}


	public static void main(String[] args) {
		try
		{
			solution();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}

}
728x90
저작자표시 비영리

'Algorithm > 문제 풀이' 카테고리의 다른 글

[알고리즘] 리모컨 (백준 1107번)  (0) 2020.09.20
[알고리즘] 카드 섞기 (백준 1091번)  (0) 2020.09.19
[알고리즘] 드래곤 커브 (백준 15685번)  (0) 2020.09.18
[알고리즘] 로봇 청소기 (백준 14503번)  (0) 2020.09.17
[알고리즘] 아기상어 (백준 16236번)  (0) 2020.09.17

관련글

댓글

티스토리툴바