과거의나야도와줘
[백준 15683] 감시 (JAVA) 본문
백준(BOJ) 15683 감시
난이도
221218 기준 골드 4
사용 알고리즘
브루트포스(완전탐색)
문제 링크
https://www.acmicpc.net/problem/15683
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
풀이 과정
1. 문제 읽기(중요한 부분 굵은 표시)
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.
1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.
CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.
CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.
사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.
CCTV의 최대 개수는 8개를 넘지 않는다.
출력
첫째 줄에 사각 지대의 최소 크기를 출력한다.
2. 어떤 알고리즘을 사용할 것인가
우리가 정해야 하는 것은 CCTV의 방향입니다. 1,3,4번 CCTV는 회전에 따라 4개의 종류가 나올 수 있고 2번은 2개의 종류 5번은 회전을 시켜도 항상 같은 결과이기에 1개의 종류가 나옵니다.
CCTV의 최대 개수는 8개를 넘지 않기 때문에 CCTV 방향의 조합의 최대 개수는 4의 8승 = 65,536개 입니다.
따라서 직접 CCTV의 방향 조합을 완전 탐색해서 그때마다의 사각지대의 크기를 구해도 시간초과가 나지 않을 것이라 판단할 수 있습니다.
3. 풀이 구상
완전 탐색은 중복순열을 이용해서 할 것입니다. CCTV의 방향을 1~4(동,서,남,북)으로 표현할 때 각 CCTV마다 1~4의 숫자중 하나를 고른다 생각하면 됩니다. 다만 CCTV중 2번과 5번은 1~4를 모두 고를 필요가 없다는 것을 반영하면 속도가 조금이라도 더 빨라 질 것입니다.
이런 구현 문제가 나올 때 저는 왠만하면 클래스를 만드는 편입니다. 이 문제에서는 CCTV 클래스를 만들면 더 깔끔한 코드가 나올 것 같습니다.
CCTV 클래스는 필드 값으로 CCTV의 위치(r,c), CCTV의 종류(1~5), CCTV의 방향(1~4)을 가지고 있을 것이고메서드는 CCTV의 방향 설정하기, 감시하는 영역 반환하기 두 가지가 있을 것입니다.
일단은 여기까지만 구상을 하고 코드를 짜보겠습니다.
4. 코드 작성
라이브 코딩 영상
이번 문제는 라이브 코딩 하는 모습을 녹화를 한 번 해봤습니다.
제가 알고리즘 문제 풀 때 어떤 생각을 하면서 푸는지 어쩌다 실수하는지 궁금해서 한 번 찍어봤는데요
중얼 중얼 하면서 문제 푸니까 문제에 집중도 잘되고 좋네요 여러분들도 유튜브는 안올리더라도 영상 찍어보면서 문제 푸시는 것도 좋은 공부 방법인 것 같아 추천드립니다.
유튜브에서 자체적으로 볼륨을 줄이는 기능이 있어 목소리가 잘 안들리네요
다음번에는 해결해서 올려보겠습니다
1. 정답 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
// 백준 15683번 감시 라이브 코딩
public class Main {
static int N, M;
static int[][] board;
static List<CCTV> cctvLs;
static boolean[][] watched;
static int resultMin;
// 중복순열 결과 담을 배열
static int[] permArr;
// 4방탐색 상우하좌 (1,2,3,4)
static int[] dr = {0,-1,0,1,0};
static int[] dc = {0,0,1,0,-1};
static class CCTV {
int r;
int c;
// 1~5
int type;
// 생성자
public CCTV(int r, int c, int type) {
this.r = r;
this.c = c;
this.type = type;
}
// 감시하는 영역 반환 메소드
public void watchArea(int direction) {
if(type == 1) {
watchAreaModule(this.r, this.c, direction);
} else if(type == 2) {
for(int d = 1; d <=4; d++) {
if((direction % 2)!=(d % 2)) {
continue;
}
watchAreaModule(this.r, this.c, d);
}
} else if(type == 3) {
watchAreaModule(this.r, this.c, direction);
int next = (direction+1) % 5;
if(next == 0) {
next = 1;
}
watchAreaModule(this.r, this.c, next);
} else if(type == 4) {
for(int d = 1; d <=4; d++) {
if(d==direction) {
continue;
}
watchAreaModule(this.r, this.c, d);
}
} else if(type == 5) {
for(int d = 1; d <=4; d++) {
watchAreaModule(this.r, this.c, d);
}
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
board = new int[N][M];
cctvLs = new ArrayList<CCTV>();
for(int r = 0; r < N; r++) {
st = new StringTokenizer(br.readLine());
for(int c = 0; c < M; c++) {
int num = Integer.parseInt(st.nextToken());
board[r][c] = num;
if(num >= 1 && num <= 5) {
cctvLs.add(new CCTV(r,c,num));
}
}
}
permArr = new int[cctvLs.size()];
resultMin = Integer.MAX_VALUE;
// 중복순열
repPerm(0);
bw.write(resultMin+"");
bw.flush();
bw.close();
br.close();
}
static int cnt;
static void repPerm(int index) {
// 기저조건
if(index == cctvLs.size()) {
// cctv 사각지대 확인하고 리턴
blindSpot();
return;
}
for(int i = 1; i <= 4; i++) {
permArr[index] = i;
repPerm(index+1);
if(cctvLs.get(index).type==2) {
if(i==2){
return;
}
}
if(cctvLs.get(index).type==5) {
return;
}
if(resultMin == 0) {
return;
}
}
}
static void blindSpot() {
watched = new boolean[N][M];
for(int i = 0, size = cctvLs.size(); i < size; i++) {
cctvLs.get(i).watchArea(permArr[i]);
}
int blindSpotCnt = 0;
for(int r = 0; r < N; r++) {
for(int c = 0; c < M; c++) {
if(watched[r][c]==false && board[r][c]==0) {
blindSpotCnt++;
}
}
}
resultMin = Math.min(resultMin, blindSpotCnt);
}
static boolean inRange(int nr, int nc) {
if(nr >= 0 && nr < N && nc >= 0 && nc < M) {
return true;
} else {
return false;
}
}
static void watchAreaModule(int r, int c, int direction){
int dist = 0;
int nr = r + dr[direction]*dist;
int nc = c + dc[direction]*dist;
boolean meetWall = false;
while(inRange(nr,nc) && !meetWall) {
watched[nr][nc] = true;
if(board[nr][nc]==6) {
meetWall = true;
}
dist++;
nr = r + dr[direction]*dist;
nc = c + dc[direction]*dist;
}
}
}
2. 주의할 점
구현문제는 정신줄을 붙잡고 있는게 가장 중요합니다. 설계를 꼼꼼히 하고 시작하면 더 빠르게 문제를 풀 수 있습니다.
풀이 후기
이 문제는 백준에 있는 삼성 SW역량테스트 문제집에 있는 문제입니다. 정신줄 잡고 문제 풀면 빠른시간내에 문제를 풀 수 있을 것이라 봅니다.
'알고리즘 > 구현' 카테고리의 다른 글
| [백준 14890] 경사로 (JAVA) (1) | 2022.12.28 |
|---|---|
| [백준 20005] 보스몬스터 전리품 (JAVA) (0) | 2022.12.25 |
| [백준 14891] 톱니바퀴 (JAVA) (0) | 2022.12.22 |
| [백준 16954] 움직이는 미로 탈출 (JAVA) (0) | 2022.12.21 |
| [백준 19236] 청소년 상어 (JAVA) (1) | 2022.12.19 |