본문 바로가기
알고리즘 문제/백준

[백준 - Java] 15683번 : 감시 (삼성 SW 역량 테스트 기출 문제)

by 건복치 2021. 2. 11.
반응형

문제

www.acmicpc.net/problem/15683

 

15683번: 감시

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

www.acmicpc.net

설명

헷갈려서 엄청 오래 걸린 문제다...

근데 진짜 말그대로 1~5번까지 cctv를 90도씩 돌려가며 조합해서 사각지대의 최솟값을 구해야 한다.

 

방향을 바꾸는 과정은 시계방향으로 상 우 좌 하로 0, 1, 2, 3 순서이다.

(순서는 그냥 자기 마음대로 정해면 됨 나는 상우하좌가 편해서 저렇게 외웠다!)

 

CCTV는 1~5까지 총 5개의 형태가 있다.

각각의 경우를 90도 회전하는 경우를 생각해보면 아래와 같이 나타낼 수 있다.

 

 

1번의 경우 4가지, 2번 2가지, 3번 4가지, 4번 4가지, 5번 1가지의 경우가 나온다.

하지만 편의를 위해 상 우 하 좌 4방향이 있다고 가정하고, 방향이 있다면 1 없다면 0으로 나타낸다면

화살표 밑의 () 소괄호처럼 표현할 수 있다.

 

 

예를 들어 1번과 2번 CCTV를 가진 사무실이 있다면

1번 카메라로 나올 수 있는 방향 가짓수는 4,

2번 카메라로 나올 수 있는 방향 가지수는 2로 총 8가지의 경우의 수가 나오고

이 8가지를 바탕으로 감시를 하고, 가장 최소 사각지대를 가진 경우가 정답이 되는 것이다.

 

즉, 1~5까지의 CCTV가 가지는 방향에 대한 순열을 구한다고 생각하면 모든 경우를 구할 수 있다.

순열은 n개의 값 중에서 r개의 숫자를 순서대로 뽑는 경우를 말한다.

이를 적용해 4개의 방향 중에서 CCTV의 총 개수 r만큼을 순서대로 뽑아 나올 수 있는 모든 방향의 경우를 따져보는 것!

DFS를 이용해 순열을 구해준다. 

 

예를 들어 1~3까지의 CCTV가 있다면

(0, 0, 0), (0, 0, 1) (0, 0, 2)... (0, 1, 1)... (1, 1, 1) ... (3, 3, 3)

 

1~5까지의 CCTV가 있다면

(0, 0, 0, 0, 0)... (0, 1, 2, 2, 3)... (3, 3, 3, 3, 3)

 

* 순열에 관해 더 자세히 알고 싶다면 아래 포스트 참고

 

[Java] 순열 Permutation

 

public static void permutation(int depth, int r) {
	if(depth == r) {
		// Copy original 'map' array
		copyMap = new int[N][M];
		for(int i = 0; i < map.length; i++) {
			System.arraycopy(map[i], 0, copyMap[i], 0, map[i].length);
		}

		// cctv번호와 순열로 뽑혀진 방향에 맞는 상하좌우 방향 설정 
		for(int i = 0; i < cctvList.size(); i++) {
			direction(cctvList.get(i), output[i]);
		}

		// 사각 지대 구하기 
		getBlindSpot();

		return;
	}

	for(int i = 0; i < 4; i++) {
		output[depth] = i;
		permutation(depth+1, r);
	}
}

 

depth가 r과 같아졌다는 것은 r만큼의 순열을 모두 뽑았다는 것.

이때 기존의 사무실을 구성하는 map 배열을 복사한다.

기존 map 배열은 건들지 말고, 복사한 배열에서 감시를 수행해 총 몇 개의 사각지대가 나오는지 판별한다.

 

그다음, direction 함수에서 CCTV번호에 맞는 방향을 지정한다.

 

// 각 cctv 번호와 순열로 뽑혀진 방향에 맞게 감시 
public static void direction(CCTV cctv, int d) {
	int cctvNum = cctv.num;

	if(cctvNum == 1) {
		if(d == 0) watch(cctv, 0); // 상 
		else if(d == 1) watch(cctv, 1); // 우 
		else if(d == 2) watch(cctv, 2); // 하  
		else if(d == 3) watch(cctv, 3); // 좌 
	} else if(cctvNum == 2) {
		if(d == 0 || d == 2) {
			watch(cctv, 0); watch(cctv, 2); // 상하 
		} else {
			watch(cctv, 1); watch(cctv, 3); // 좌우 
		}
	} else if(cctvNum == 3) {
		if(d == 0) {
			watch(cctv, 0); // 상우 
			watch(cctv, 1);
		} else if(d == 1) { 
			watch(cctv, 1); // 우하 
			watch(cctv, 2);
		} else if(d == 2) { 
			watch(cctv, 2); // 하좌 
			watch(cctv, 3);
		} else if(d == 3) { 
			watch(cctv, 0); // 좌상 
			watch(cctv, 3);
		}
	} else if(cctvNum == 4) {
		if(d == 0) {
			watch(cctv, 0); // 좌상우 
			watch(cctv, 1);
			watch(cctv, 3);
		} else if(d == 1) {
			watch(cctv, 0); // 상우하 
			watch(cctv, 1);
			watch(cctv, 2);
		} else if(d == 2) {
			watch(cctv, 1); // 좌하우 
			watch(cctv, 2);
			watch(cctv, 3);
		} else if(d == 3) {
			watch(cctv, 0); // 상좌하 
			watch(cctv, 2);
			watch(cctv, 3);
		}
	} else if(cctvNum == 5) { // 상우하좌
		watch(cctv, 0);
		watch(cctv, 1);
		watch(cctv, 2);
		watch(cctv, 3);
	}
}

 

CCTV의 번호와 뽑힌 방향에 맞게 감시를 한다.

watch 함수에 현재 CCTV 정보와 확인할 방향을 주어 본격적으로 감시를 수행한다.

 

// BFS로 방향에 맞게 감시 
public static void watch(CCTV cctv, int d) {
	Queue<CCTV> queue = new LinkedList<>();
	boolean[][] visited = new boolean[N][M];

	queue.add(cctv);
	visited[cctv.x][cctv.y] = true;

	while(!queue.isEmpty()) {
		int nx = queue.peek().x + dx[d];
		int ny = queue.poll().y + dy[d];

		if(nx < 0 || nx >= N || ny < 0 || ny >= M || copyMap[nx][ny] == 6) { // 범위를 벗어나거나 벽을 만나면 끝 
			break;
		}

		if(copyMap[nx][ny] == 0) { 
			copyMap[nx][ny] = -1; // 빈칸이라면 감시할 수 있다는 의미로 -1 
			queue.add(new CCTV(cctv.num, nx, ny));
		} else { // 다른 cctv가 있거나 이미 감시된 칸이라면 
			queue.add(new CCTV(cctv.num, nx, ny)); // 그냥 통과 
		}
	}
}

 

BFS를 이용해 CCTV의 시작 위치에서부터 각 방향에 맞게 한 칸씩 이동한다.

범위를 벗어나거나 벽을 만나면 끝난다.

빈칸을 만나면 감시할 수 있기에 copyMap의 값을 -1로 만들어준다.

다른 CCTV를 만나거나 이미 감시된 칸이라면 그냥 통과하고 큐에 새로운 좌표만 넣어준다.

 

BFS가 모두 수행된 뒤에 copyMap을 순회하며 총 몇 개의 사각지대가 있는지 구하고, 최솟값을 정답으로 갱신한다. 

전체 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static int N, M;
	public static int[][] map;
	public static int[][] copyMap;
	public static int[] output;
	public static ArrayList<CCTV> cctvList;
	public static int[] dx = {-1, 0, 1, 0}; // 상 우 하 좌 시계방향 순서 
	public static int[] dy = {0, 1, 0, -1};
	public static int answer = Integer.MAX_VALUE;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		map = new int[N][M];
		cctvList = 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] != 0 &&  map[i][j] != 6) {
					cctvList.add(new CCTV(map[i][j], i, j));
				}
			}
		}

		output = new int[cctvList.size()]; // 순열을 담을 배열 
		permutation(0, cctvList.size());

		System.out.println(answer);
	}

	// DFS로 상하좌우 4방향 중에서 cctv의 총 개수, r만큼을 순서대로 뽑는 순열을 구함 
	public static void permutation(int depth, int r) {
		if(depth == r) {
			// Copy original 'map' array
			copyMap = new int[N][M];
			for(int i = 0; i < map.length; i++) {
				System.arraycopy(map[i], 0, copyMap[i], 0, map[i].length);
			}
						
			// cctv번호와 순열로 뽑혀진 방향에 맞는 상하좌우 방향 설정 
			for(int i = 0; i < cctvList.size(); i++) {
				direction(cctvList.get(i), output[i]);
			}
			
			// 사각 지대 구하기 
			getBlindSpot();

			return;
		}
		
		for(int i = 0; i < 4; i++) {
			output[depth] = i;
			permutation(depth+1, r);
		}
	}

	// 각 cctv 번호와 순열로 뽑혀진 방향에 맞게 감시 
	public static void direction(CCTV cctv, int d) {
		int cctvNum = cctv.num;

		if(cctvNum == 1) {
			if(d == 0) watch(cctv, 0); // 상 
			else if(d == 1) watch(cctv, 1); // 우 
			else if(d == 2) watch(cctv, 2); // 하  
			else if(d == 3) watch(cctv, 3); // 좌 
		} else if(cctvNum == 2) {
			if(d == 0 || d == 2) {
				watch(cctv, 0); watch(cctv, 2); // 상하 
			} else {
				watch(cctv, 1); watch(cctv, 3); // 좌우 
			}
		} else if(cctvNum == 3) {
			if(d == 0) {
				watch(cctv, 0); // 상우 
				watch(cctv, 1);
			} else if(d == 1) { 
				watch(cctv, 1); // 우하 
				watch(cctv, 2);
			} else if(d == 2) { 
				watch(cctv, 2); // 하좌 
				watch(cctv, 3);
			} else if(d == 3) { 
				watch(cctv, 0); // 좌상 
				watch(cctv, 3);
			}
		} else if(cctvNum == 4) {
			if(d == 0) {
				watch(cctv, 0); // 좌상우 
				watch(cctv, 1);
				watch(cctv, 3);
			} else if(d == 1) {
				watch(cctv, 0); // 상우하 
				watch(cctv, 1);
				watch(cctv, 2);
			} else if(d == 2) {
				watch(cctv, 1); // 좌하우 
				watch(cctv, 2);
				watch(cctv, 3);
			} else if(d == 3) {
				watch(cctv, 0); // 상좌하 
				watch(cctv, 2);
				watch(cctv, 3);
			}
		} else if(cctvNum == 5) { // 상우하좌
			watch(cctv, 0);
			watch(cctv, 1);
			watch(cctv, 2);
			watch(cctv, 3);
		}
	}
	
	// BFS로 방향에 맞게 감시 
	public static void watch(CCTV cctv, int d) {
		Queue<CCTV> queue = new LinkedList<>();
		boolean[][] visited = new boolean[N][M];

		queue.add(cctv);
		visited[cctv.x][cctv.y] = true;

		while(!queue.isEmpty()) {
			int nx = queue.peek().x + dx[d];
			int ny = queue.poll().y + dy[d];

			// 범위를 벗어나거나 벽을 만나면 끝 
			if(nx < 0 || nx >= N || ny < 0 || ny >= M || copyMap[nx][ny] == 6) { 
				break;
			}

			if(copyMap[nx][ny] == 0) { 
				copyMap[nx][ny] = -1; // 빈칸이라면 감시할 수 있다는 의미로 -1 
				queue.add(new CCTV(cctv.num, nx, ny));
			} else { // 다른 cctv가 있거나 이미 감시된 칸이라면 
				queue.add(new CCTV(cctv.num, nx, ny)); // 그냥 통과 
			}
		}
	}
	
	// 사각 지대 구하기 
	public static void getBlindSpot() {
		int cnt = 0;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(copyMap[i][j] == 0) {
					cnt++;
				}
			}
		}
		answer = Math.min(answer, cnt);
	}


}

class CCTV {
	int num;
	int x;
	int y;

	CCTV(int num, int x, int y) {
		this.num = num;
		this.x = x;
		this.y = y;
	}
}

GITHUB

 

 

KwonMinha/BOJ

Baekjoon Online Judge(Java) 문제풀이. Contribute to KwonMinha/BOJ development by creating an account on GitHub.

github.com

 

반응형

댓글