문제 >
스타트링크의 사무실은 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번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.
CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 벽을 감시할 수 없다.
위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.
CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.
위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.
사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.
입력 >
첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.
CCTV의 최대 개수는 8개를 넘지 않는다.
출력 >
첫째 줄에 사각 지대의 최소 크기를 출력한다.
해결방법 >
DFS(깊이우선탐색) 알고리즘으로 각 CCTV의 방향을 설정했을 때 나올 수 있는 모든 경우의 수를 찾고 그 중 최소의 사각지대를 출력한다.
사무실에 대한 정보를 2차원 배열로 저장할 때, CCTV에 대한 좌표값과 번호를 저장한다.
저장된 CCTV를 하나씩 가능한 모든 경우에 따라 설치해본다.
각 CCTV의 번호에 따라 가능한 경우는 아래와 같다.
1번 CCTV > 동 / 서 / 남 / 북 (4 가지)
2번 CCTV > 동 - 서 / 남 - 북 (2 가지)
3번 CCTV > 북 - 동 / 동 - 남 / 남 - 서 / 서 - 북 (4 가지)
4번 CCTV > 서 - 북 - 동 / 북 - 동 - 남 / 동 - 남 - 서 / 남 - 서 - 북 (4 가지)
5번 CCTV > 동 - 서 - 남 - 북 (1 가지)
각 CCTV마다 한 가지 경우를 선택해 깊이우선탐색을 하고 마지막 CCTV를 선택했을 때 사각지대의 수를 구한다.
모든 가능한 경우를 탐색했을 때 사각지대의 최소값을 출력한다.
아래의 두 코드는 사실 메모리 사용량이나 시간에 차이는 없는데
단지 첫 번째 코드길이가 다른 분들이 제출한거에 비해 몇 배는 긴 거 같아서
다시 작성한 게 두 번째 코드....
되추적 알고리즘을 함께 사용하는 방법도 있는 거 같다.
이 문제는 다시 한 번 풀어봐야겠다
[JAVA]
package baekjoon;
import java.util.*;
public class BOJ_15683 {
static int[][] map;
static ArrayList<Node> camera;
static int n;
static int m;
static int min;
public static class Node{
int x;
int y;
int k;
Node(int x, int y, int k){
this.x = x;
this.y = y;
this.k = k;
}
}
public static void see(int x, int y, int dx, int dy, int[][] v) {
int nx = x + dx;
int ny = y + dy;
while(nx >= 0 && ny >= 0 && nx < n && ny < m && map[nx][ny] != 6) {
v[nx][ny] = 1;
nx += dx;
ny += dy;
}
}
public static void dfs(Node node, int flag, int[][] v, int idx) {
int[][] visit = new int[n][m];
int x = node.x;
int y = node.y;
int k = node.k;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
visit[i][j] = v[i][j];
}
}
visit[x][y] = 1;
if(k == 1) {
if(flag == 0) {
see(x, y, -1, 0, visit);
}
else if(flag == 1) {
see(x, y, 0, 1, visit);
}
else if(flag == 2) {
see(x, y, 1, 0, visit);
}
else {
see(x, y, 0, -1, visit);
}
}
else if(k == 2){
if(flag == 0) {
see(x, y, 0, -1, visit);
see(x, y, 0, 1, visit);
}
else {
see(x, y, -1, 0, visit);
see(x, y, 1, 0, visit);
}
}
else if(k == 3) {
if(flag == 0) {
see(x, y, -1, 0, visit);
see(x, y, 0, 1, visit);
}
else if(flag == 1) {
see(x, y, 0, 1, visit);
see(x, y, 1, 0, visit);
}
else if(flag == 2) {
see(x, y, 1, 0, visit);
see(x, y, 0, -1, visit);
}
else {
see(x, y, 0, -1, visit);
see(x, y, -1, 0, visit);
}
}
else if(k == 4) {
if(flag == 0) {
see(x, y, 0, -1, visit);
see(x, y, -1, 0, visit);
see(x, y, 0, 1, visit);
}
else if(flag == 1) {
see(x, y, -1, 0, visit);
see(x, y, 0, 1, visit);
see(x, y, 1, 0, visit);
}
else if(flag == 2) {
see(x, y, 0, 1, visit);
see(x, y, 1, 0, visit);
see(x, y, 0, -1, visit);
}
else {
see(x, y, 1, 0, visit);
see(x, y, 0, -1, visit);
see(x, y, -1, 0, visit);
}
}
else {
see(x, y, -1, 0, visit);
see(x, y, 0, 1, visit);
see(x, y, 1, 0, visit);
see(x, y, 0, -1, visit);
}
if(idx == camera.size()) {
int cnt = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(map[i][j] != 6 && visit[i][j] == 0) {
cnt++;
}
}
}
min = Math.min(cnt, min);
return;
}
node = camera.get(idx);
k = node.k;
if(k == 1 || k == 3 || k == 4) {
dfs(node, 0, visit, idx+1);
dfs(node, 1, visit, idx+1);
dfs(node, 2, visit, idx+1);
dfs(node, 3, visit, idx+1);
}
else if(k == 2) {
dfs(node, 0, visit, idx+1);
dfs(node, 1, visit, idx+1);
}
else {
dfs(node, 0, visit, idx+1);
}
}
public static void init() {
int[][] visit = new int[n][m];
Node node = camera.get(0);
int k = node.k;
if(k == 1 || k == 3 || k == 4) {
dfs(node, 0, visit, 1);
dfs(node, 1, visit, 1);
dfs(node, 2, visit, 1);
dfs(node, 3, visit, 1);
}
else if(k == 2) {
dfs(node, 0, visit, 1);
dfs(node, 1, visit, 1);
}
else {
dfs(node, 0, visit, 1);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
map = new int[n][m];
min = 0;
camera = new ArrayList<>();
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
map[i][j] = sc.nextInt();
if(map[i][j] >= 1 && map[i][j] <= 5)
camera.add(new Node(i, j, map[i][j]));
if(map[i][j] == 0)
min++;
}
}
if(camera.size() > 0) init();
System.out.println(min);
}
}
package baekjoon;
import java.util.*;
public class BOJ_15683_2 {
static int n;
static int m;
static int[][] map;
static ArrayList <Camera> list = new ArrayList<>();
static int min = 0;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int[][] one = {{0}, {1}, {2}, {3}};
static int[][] two = {{0, 2}, {1, 3}};
static int[][] three = {{0, 1}, {1, 2}, {2, 3}, {3, 0}};
static int[][] four = {{0, 1, 2}, {1, 2, 3}, {2, 3, 0}, {3, 0, 1}};
static int[][] five = {{0, 1, 2, 3}};
public static class Camera{
int x;
int y;
int num;
Camera(int x, int y, int num){
this.x = x;
this.y = y;
this.num = num;
}
}
public static void set(Camera c, int idx, int flag, int[][] num, int[][] v) {
int[][] visit = new int[n][m];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
visit[i][j] = v[i][j];
}
}
visit[c.x][c.y] = 1;
for(int i = 0; i < num[flag].length; i++) {
int nx = c.x + dx[num[flag][i]];
int ny = c.y + dy[num[flag][i]];
while(nx >= 0 && ny >= 0 && nx < n && ny < m && map[nx][ny] != 6) {
visit[nx][ny] = 1;
nx += dx[num[flag][i]];
ny += dy[num[flag][i]];
}
}
classify(idx+1, visit);
}
public static void classify(int idx, int[][] v) {
if(idx == list.size()) {
int cnt = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(map[i][j] != 6 && v[i][j] == 0)
cnt++;
}
}
min = Math.min(min, cnt);
return;
}
Camera c = list.get(idx);
int[][] visit = new int[n][m];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
visit[i][j] = v[i][j];
}
}
switch(c.num) {
case 1:
for(int i = 0; i < 4; i++) {
set(c, idx, i, one, visit);
}
break;
case 2:
for(int i = 0; i < 2; i++) {
set(c, idx, i, two, visit);
}
break;
case 3:
for(int i = 0; i < 4; i++) {
set(c, idx, i, three, visit);
}
break;
case 4:
for(int i = 0; i < 4; i++) {
set(c, idx, i, four, visit);
}
break;
case 5:
set(c, idx, 0, five, visit);
break;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
map = new int[n][m];
int[][] visit = new int[n][m];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
map[i][j] = sc.nextInt();
if(map[i][j] >= 1 && map[i][j] <= 5) {
list.add(new Camera(i, j, map[i][j]));
}
if(map[i][j] == 0) min++;
}
}
if(list.size() > 0) classify(0, visit);
System.out.println(min);
}
}
'Problem Solving > BOJ' 카테고리의 다른 글
| [백준] 14499번 - 주사위 굴리기 (0) | 2020.03.16 |
|---|---|
| [백준] 16236번 - 아기 상어 (0) | 2020.03.16 |
| [백준] 17837번 - 새로운 게임 2 (0) | 2020.03.16 |
| [백준] 17140번 - 이차원 배열과 연산 (0) | 2020.03.15 |
| [백준] 15686번 - 치킨 배달 (0) | 2020.03.14 |
댓글