안녕하세요! zzino 입니다 여러분.
오늘은 solved.ac 기준 전투력 5만 투력인 녀석을 데려왔습니다. 무려 삼성 A형 기출인 녀석이라구욧!!
바로 백준 15683 감시 입니다. 골드5면 5만 투력 맞죠?ㅋㅋㅋ
자세한 설명과 함께 다시 도전해봅시다!
https://www.acmicpc.net/problem/15683
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
자 일단 문제를 한 번 읽어봅시다.
처음 풀라고 하면 되게 갑갑~하죠??
단순히 쭉 뻗어나가는거 자체는 떠올려보니 쉬울거같습니다. 그죠? 그냥 0인 지점을 #으로 바꿔주고 6이면 break걸고. 대충 시나리오는 떠오르죠? 여기서 생각 더하면 복잡해질것같으니 대~강 밑그림만 잡아놓고 넘어갑시다!
그런데 문제는 말이죠..
이거를 어떻게 구현해야하나...각각의 경우를 어떻게 구별하지? 모든 경우를 다 봐야되나? cctv 종류마다 바라보는 방향이 다른데 이건 어떻게 구현하지? 심지어 각cctv마다 방향에 따라서 또 달라지네? 어떻게 꼼수 못쓰나? 최적화 못하나? 이런 고민들이 떠오르죠??
자자...여러분!!!
처음 풀때는 그렇게 많은 고민하면 머리만 복잡해집니다. 각각의 cctv에서 뻗어나가는 함수의 로직은 아까도 말씀드렸듯이 대~강만 밑그림 잡는다는 생각으로 잡아놓고, 큰거부터 고민해봅시다. 최적화같은 것도 나중에 생각합시다.
혹시 떠오른게 있다면 메모만 해놓고 넘어가도록 합시다!
그럼 어떻게 해야하나? 우선 컴퓨터스럽게 한번 생각해봅시다!
가령 cctv 종류가 1, 4이고 cctv가 2개밖에 없다면, 우리는 사실 머릿속으로 cctv가 어느 방향을 볼때 사각지대가 제일 적은지 어렴풋이 알고 있죠? 머리좋으신분이라면 아마 바로 최적의 경우를 뽑아낼지도 모르죠?
근데 컴퓨터는 이걸 어떻게 알까요?
답은 간단합니다. 모든 경우를 다 해보는거죠.
초당 억단위의 연산이 가능한 컴퓨터를 혹사시켜봅시다 ㅎㅎ(물론 시간제한을 고려해야하지만요)
그럼 이문제도 어떻게 풀어야 할 지 감이 오시죠? 바로, 그냥 모든 경우의 수를 다 고려해보자! 입니다.
그런데 모든 경우의 수를 어떻게 다 보죠? 알고리즘 푸신분이라면 해왔던 거 있지 않나요? 바로 백트랙킹!
그래서 주인장 zzino는 모든 후보군을 다 검사해본다는 idea에 착안해 처음에는 백트랙킹을 시도했어요. 그런데 백트랙킹을 시도하니까 깊이, depth를 한 칸 내려가고 처리하고 다시 깊이를 올라오는 과정에서 원상태로 복구하게 하는걸 도저히 못짜겠더라고요ㅋㅋㅠㅠ 무슨 말이냐면요,
N-Queens 를 예로들면 한 행에서 그 다음행으로 퀸을 놓을때 퀸을 놓고나서 처리하고 다시 올라올때, 깊이를 다시 올라오는 과정은 단순히 퀸을 제거해주면 되는데 여기서는 사각지대가 아니다 라는 표시의 '#'을 지우는게 너무 힘들더라구요 ㅠㅠ ㅋㅋㅋ
혹시 아시는 분 있으면 한번 댓글 남겨주십쇼!!
그런데 여러분, 모든 백트랙킹은 for문으로 바꿀수있는것 아시죠?!
그래서 zzino는 반복문으로 다시 도전했습니다!
다시말해, for문으로 모든 경우의 수를 다 보는거죠.!
즉, 만약 cctv가 8개 있으면 4^8 개의 경우를 다 확인해보는거죠. 왜냐면 각각의 cctv마다 4방향을 가지고 있으니까요.
그럼 일단 cctv가 8개 있다면 main문에 for(int i = 0; i < 4^8; i++) 이렇게 적어야겠다 라는건 느낌이 왔죠?
그럼 cctv개수가 안정해져있으면 어떻게 할까요?
4^k 이런식으로 적어도 되겠죠? 자바에는 Math.pow도 있고요!
그런데 여러분 Math.pow 를 쓸때는 조금 조심하셔야되요. 컴퓨터는 IEEE표준에 따른 저장방식 때문에 어쩔 수 없이 실수에 오차가 존재하거든요 ㅠㅠ
그래서 정확한 정수 거듭제곱 연산을 하고 싶으시다면, 비트연산자를 쓰셔야 합니다! 이번 기회에 알아봐요 ㅎㅎ
자자 어떻게 하냐면요,
"1 << k" 이렇게 적으면 2^k 를 나타낼 수 있습니다. 즉, 비트단위에서 1을 k칸 만큼 왼쪽으로 이동시킨다는 뜻입니다.
아쉽게도 2의 배수가 아니라면 좀 힘듭니다 ㅠ
하지만 문제에서는 지수의 밑이 4니까 괜찮겠죠?
저희가 나타내고 싶은건, cctv개수가 k개 라면 4^k 를 나타내고 싶은거니까 어떻게 쓰면 될까요?
이건 고민한번 해보세요~ ㅎㅎ 모르겠으면 아래로 가서 코드봅시다!
자 그럼 다음 토픽으로 넘어가봅시다.
그럼 "각각의 경우"는 이제 for문으로 구분을 할 수 있겠는데, 이를 테면 for문의 변수가 i면 이 i를 어떻게 활용해야 유의미한 정보(각각의 경우를 구분)를 얻어낼 수 있을가요?
여기서 비트마스킹이라는 테크닉이 나오는데요, 이는 그림으로 보여드리는게 더 빠를것같아 준비해봤습니다!
구현은 어떻게 할지 한 번 잘 생각해보세요 ㅎㅎ
다음으로 이제 사각지대를 메워나가는 fill() 함수 를 구현해볼건데요, 여기서 많은 고민이 떠오릅니다.
뭐나면요, 아 이거를 각각의 방향마다 따로 구현해야하나? 아니면 합쳐서 구현할 수 있나? 라는 고민이 떠오릅니다.
주인장 zzino는 재사용성을 고려해 어떤 방향이든 매개변수로 방향을 받아 한 방향으로 뻗어나가는 함수로 fill을 정의하고 구현에 들어갔어요. 로직 자체는 쉬운편이라 혼자 짜보시는걸 추천드릴게요.
힌트를 드리면 , 특정 방향으로 뻗어가나게 하기 위해 방향벡터인 dx, dy 배열을 사용하시는 걸 추천드릴게요.
말은 방향벡터라고 했지만 그냥 간단합니다 :) 말이 거창해요 말이.
이제 코드를 봐볼까요??
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int[][] board;
static int[][] tempBoard;
static int N;
static int M;
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());
ArrayList<cctv> cctvs = new ArrayList<>();
int min = 0;
board = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
if (board[i][j] != 0 && board[i][j] != 6) {
cctvs.add(new cctv(i, j, board[i][j]));
}
if(board[i][j] == 0) min++;
}
}
if (min == 0) {
System.out.println(min);
System.exit(0);
}
for (int i = 0; i < (1 << (2 * cctvs.size())); i++) {
int temp = i;
tempBoard = new int[N][M];
for (int k = 0; k < N; k++) {
System.arraycopy(board[k], 0, tempBoard[k], 0, M);
}
for (int j = 0; j < cctvs.size(); j++) {
int kind = cctvs.get(j).kind;
int x = cctvs.get(j).x;
int y = cctvs.get(j).y;
int dir = temp % 4;
temp /= 4;
if (kind == 1) {
fill(dir,x,y);
} else if (kind == 2) {
fill(dir,x,y);
fill(dir + 2,x,y);
} else if (kind == 3) {
fill(dir, x, y);
fill(dir + 1, x, y);
} else if (kind == 4) {
fill(dir, x, y);
fill(dir + 1, x, y);
fill(dir + 2, x, y);
} else {
fill(dir, x, y);
fill(dir + 1, x, y);
fill(dir + 2, x, y);
fill(dir + 3, x, y);
}
}
int count = 0;
for (int j = 0; j < N; j++) {
for (int k = 0; k < M; k++) {
if (tempBoard[j][k] == 0) {
count++;
}
}
}
min = Math.min(count, min);
if (min == 0) {
System.out.println(min);
System.exit(0);
}
}
System.out.println(min);
}
//머릿속에 4방향 한번에? 띠로따로? 가 떠오르겠지만 you can do it!!!e
// fill 함수 구현은...dir 방향에 따라서 한방향으로 쭉 채워주는 함수.
//fill 구현시 아무 한 방향으로 구현만 해놓으면, 그냥 쭈루룩 되겠지?!
static void fill(int dir,int x, int y) {
dir %= 4;
for (int i = 0; i < 8; i++) {
x += dx[dir]; //실수
y += dy[dir];
if (0 <= x && x < N && 0 <= y && y < M) {
if (tempBoard[x][y] == 0) { //tempBoard 지 board아님.
tempBoard[x][y] = 7;
} else if (tempBoard[x][y] == 6) {
return;
}
}
}
}
static class cctv {
int x;
int y;
int kind;
cctv(int x, int y, int kind) {
this.x = x;
this.y = y;
this.kind = kind;
}
}
}
여기서 몇 가지 눈여겨 볼 점이 있는데요,
1, Line 30, 112
저는 cctv들의 정보를 저장하기 위해 클래스를 정의하고, 이를 ArrayList에 담았는데요,
그냥 cctv 개수 X 3 사이즈의 2차원 배열을 만들어서
0열에 cctv 종류 저장, 1열에 cctv x좌표, 2열에 cctv y좌표를 저장해도 됩니다!
2, Line32
cctv가 한 개도 없는 경우를 대비해 저렇게 미리 셌습니다. cctv가 한개도없으면 min이 정답이겠죠?
3, Line 44
아까 제가 백트랙킹에서 깊이를 다시 올라오는 과정이 회복이 안된다고 말씀드렸죠?
그냥 여기서는 무식하게 한 번 for문 돌때마다, 즉 한 경우의 수를 해볼때마다 board 배열을 새로 잡습니다.
tempBoard 배열로요! ㅎㅎ
4, Line 53,54
이게 아까 말씀드린 비트마스킹을 이용해 각각의 경우의 수를 구분하는 과정입니다!
for문 돌때마다 각 cctv의 방향을 뽑아낼 수 있죠?
5, Line 104
여기서 문제처럼 #으로 하지마시고 그냥 안쓰는 숫자인 7로 넣어줍시다 ㅎㅎ
고생하셨습니다 여러분! 힘들어도 한번만 더 도전해보고 안되면 그냥 바로 봅시다 ㅎㅎ 코드보는거에 죄책감 가지지 맙시다! :)