BOJ 15683

2021-01-26

백준

위 문제는 백준 사이트의 알고리즘 15683 문제에 관한 설명입니다.

문제

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는

N×M 크기의 직사각형으로 나타낼 수 있다.

사무실에는 총 K개의 CCTV가 설치되어져 있는데,

CCTV는 5가지 종류가 있다.

각 CCTV가 감시할 수 있는 방법은 다음과 같다.

1번 CCTV는 한 쪽 방향만 감시할 수 있다.

2번과 3번은 두 방향을 감시할 수 있는데,

2번은 감시하는 방향이 서로 반대방향이어야 하고,
3번은 직각 방향이어야 한다.
4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다.

사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다.

CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며,

감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 ‘#’로 나타내면 아래와 같다.

0 0 0 0 0
0 0 0 0 0
0 1 # 6 0
0 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 0 0
0 # 0 0 0
0 1 0 6 0
0 0 0 0 0
상

0 0 0 0 0
0 0 0 0 0
0 1 0 6 0
0 # 0 0 0
하

CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때

6의 오른쪽에 있는 벽을 감시할 수 없다.

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때,

CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다.

0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.

CCTV의 최대 개수는 8개를 넘지 않는다.

출력

첫째 줄에 사각 지대의 최소 크기를 출력한다.

package 삼성기출;

import java.util.List;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class BOJ15683감시 {
	static int N;
	static int M;
	static int[][] map;
	static int size;
	static List<cctvClass> cctvs = new ArrayList<>();
	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	static int answer = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		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 (1 <= map[i][j] && map[i][j] <= 5)
					cctvs.add(new cctvClass(i, j, map[i][j]));

			}
		}
		size = cctvs.size();// 사이즈
		dfs(0);
		System.out.println(answer);
	}

	static void dfs(int count) {
		if (count == size) {
			int[][] tempMap = new int[N][M];
			for (int i = 0; i < N; i++) {
				tempMap[i] = map[i].clone();
			}
			tempMap = setArea(tempMap);
			int sum = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (tempMap[i][j] == 0)
						sum++;
				}
			}
			answer = Math.min(sum, answer);
		} else {
			cctvClass cctv;
			cctv = cctvs.get(count);
			int[] temp = cctv.dir;
			if (cctv.kinds == 1 || cctv.kinds == 3 || cctv.kinds == 4) {
				for (int dir = 0; dir < 4; dir++) {
					for (int i = 0; i < cctv.dir.length; i++) {
						cctv.dir[i] += dir;
						cctv.dir[i] = cctv.dir[i] % 4;
					}
					dfs(count + 1);
					cctv.dir = temp;
				}
			} else if (cctv.kinds == 2) {
				for (int dir = 0; dir < 2; dir++) {
					for (int i = 0; i < cctv.dir.length; i++) {
						cctv.dir[i] += dir;
						cctv.dir[i] = cctv.dir[i] % 4;
					}
					dfs(count + 1);
					cctv.dir = temp;
				}
			} else if (cctv.kinds == 5) {
				dfs(count + 1);
			}
		}
	}

	static int[][] setArea(int[][] tempMap) {
		cctvClass cctv;
		for (int i = 0; i < size; i++) {
			cctv = cctvs.get(i);
			int dir;
			for (int j = 0; j < cctv.dir.length; j++) {
				dir = cctv.dir[j];
				int nextX = cctv.x;
				int nextY = cctv.y;
				while (true) {
					nextX += dx[dir];
					nextY += dy[dir];
					if (isIn(nextX, nextY)) {
						if (tempMap[nextX][nextY] == 0) {
							tempMap[nextX][nextY] = 7;
						} else if (map[nextX][nextY] == 6)
							break;
					} else {
						break;
					}
				}
			}
		}
		return tempMap;
	}

	static boolean isIn(int x, int y) {
		if (x < 0 || N <= x || y < 0 || M <= y) {
			return false;
		}
		return true;
	}

	static class cctvClass {
		int x;
		int y;
		int kinds;
		int[] dir;

		cctvClass(int x, int y, int kinds) {
			this.x = x;
			this.y = y;
			this.kinds = kinds;

			if (kinds == 1) {
				this.dir = new int[1];
				dir[0] = 0;
			} else if (kinds == 2) {
				this.dir = new int[2];
				dir[0] = 0;
				dir[1] = 2;
			} else if (kinds == 3) {
				this.dir = new int[2];
				dir[0] = 0;
				dir[1] = 1;
			} else if (kinds == 4) {
				this.dir = new int[3];
				dir[0] = 0;
				dir[1] = 1;
				dir[2] = 2;
			} else if (kinds == 5) {
				this.dir = new int[4];
				dir[0] = 0;
				dir[1] = 1;
				dir[2] = 2;
				dir[3] = 3;
			}
		}
	}
}

이번 문제는 시뮬레이션과 DFS 문제 였습니다.

일단 cctvClass에 대해 먼저 살펴봅니다.

	static class cctvClass {
		int x;
		int y;
		int kinds;
		int[] dir;

		cctvClass(int x, int y, int kinds) {
			this.x = x;
			this.y = y;
			this.kinds = kinds;

			if (kinds == 1) {
				this.dir = new int[1];
				dir[0] = 0;
			} else if (kinds == 2) {
				this.dir = new int[2];
				dir[0] = 0;
				dir[1] = 2;
			} else if (kinds == 3) {
				this.dir = new int[2];
				dir[0] = 0;
				dir[1] = 1;
			} else if (kinds == 4) {
				this.dir = new int[3];
				dir[0] = 0;
				dir[1] = 1;
				dir[2] = 2;
			} else if (kinds == 5) {
				this.dir = new int[4];
				dir[0] = 0;
				dir[1] = 1;
				dir[2] = 2;
				dir[3] = 3;
			}
		}
	}

이 클래스에는 x좌표, y좌표, cctv의 종류가 무엇인지를 저장할 kinds라는 변수

그리고 종류에 따라 볼 수 있는 방향의 갯수가 다르니 dir[]를 배열형태로 만듭니다.

1번은 1방향
2번과 3번은 2방향이지만 반대 방향과 90도 방향
4번은 3방향
5번은 4방향을 볼 수 있도록 방향을 정해줍니다.

	static int N;
	static int M;
	static int[][] map;
	static int size;
	static List<cctvClass> cctvs = new ArrayList<>();
	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	static int answer = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		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 (1 <= map[i][j] && map[i][j] <= 5)
					cctvs.add(new cctvClass(i, j, map[i][j]));

			}
		}
		size = cctvs.size();

입력부를 살펴봅시다.

N과 M을 받고, 그 크기만큼 map을 생성합니다.

map에 들어가는 값은 0(빈공간), CCTV의 종류(1~5번), 그리고 6(벽) 이 있습니다.

CCTV인 경우에만 cctvs라는 ArrayList에 추가 해서 가지고 있습니다.

cctvs의 갯수만큼 size 변수에 추가도 해줬습니다.

이제 dfs를 이용해 봅니다.

	static void dfs(int count) {
		if (count == size) {
			int[][] tempMap = new int[N][M];
			for (int i = 0; i < N; i++) {
				tempMap[i] = map[i].clone();
			}
			tempMap = setArea(tempMap);
			int sum = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (tempMap[i][j] == 0)
						sum++;
				}
			}
			answer = Math.min(sum, answer);
		} else {
			cctvClass cctv;
			cctv = cctvs.get(count);
			int[] temp = cctv.dir;
			if (cctv.kinds == 1 || cctv.kinds == 3 || cctv.kinds == 4) {
				for (int dir = 0; dir < 4; dir++) {
					for (int i = 0; i < cctv.dir.length; i++) {
						cctv.dir[i] += dir;
						cctv.dir[i] = cctv.dir[i] % 4;
					}
					dfs(count + 1);
					cctv.dir = temp;
				}
			} else if (cctv.kinds == 2) {
				for (int dir = 0; dir < 2; dir++) {
					for (int i = 0; i < cctv.dir.length; i++) {
						cctv.dir[i] += dir;
						cctv.dir[i] = cctv.dir[i] % 4;
					}
					dfs(count + 1);
					cctv.dir = temp;
				}
			} else if (cctv.kinds == 5) {
				dfs(count + 1);
			}
		}
	}

크게 2부분으로 나뉩니다.

cctv의 갯수만큼 방향이 다 정해졌을 경우와 정해지지 않은 경우입니다.

if문

if문의 경우 cctv의 감시 방향이 다 정해져서 tempMap을 만들어 cctv가 감시할 수 있는 영역을 확인합니다.

이때 setArea함수를 이용해 감시할 수 있는 영역을 확인하고, 감시할 수 없는 부분을 0으로 해서

tempMap에 있는 0의 갯수를 다 세고, 가장 작은 값인지를

여태까지 수치중 작은 값인 answer와 비교 후 저장합니다

else if

else if문의 경우에는 cctv의 방향을 정하는 부분으로,

cctv의 종류가 1, 3, 4의 경우에는 4방향을 고려해야하고

종류가 2번인 경우에는 2방향을 고려하면됩니다.

5번인 경우는 모든 방향을 다 돌기에 갯수만 늘려준 후 dfs에 돌려줍니다.

	static int[][] setArea(int[][] tempMap) {
		cctvClass cctv;
		for (int i = 0; i < size; i++) {
			cctv = cctvs.get(i);
			int dir;
			for (int j = 0; j < cctv.dir.length; j++) {
				dir = cctv.dir[j];
				int nextX = cctv.x;
				int nextY = cctv.y;
				while (true) {
					nextX += dx[dir];
					nextY += dy[dir];
					if (isIn(nextX, nextY)) {
						if (tempMap[nextX][nextY] == 0) {
							tempMap[nextX][nextY] = 7;
						} else if (map[nextX][nextY] == 6)
							break;
					} else {
						break;
					}
				}
			}
		}
		return tempMap;
	}

이제 setArea 함수입니다.

cctv함수를 하나 만들어서 방향 별로 확인을 하고 그 방향으로 쭉나가면서

0 이라면 값을 7로 바꿔줘서 감시했다는 표시를 나타냅니다.

6 이라면 벽을 만났기 때문에 거기까지만 확인하고 break문을 이용해서 빠져나갑니다.

그리고 tempMap을 return하면 dfs함수 쪽에서는 감시된 영역을 확인 할 수 있습니다.

이 모든 것을 다 거치고 나면 answer을 출력해 줍니다.

감시

« 네트워크 - MAC Protocols with Collision(3) 네트워크 - Address Resolution Protocol »