https://www.acmicpc.net/problem/15683
사용 알고리즘
- DFS
- 백트래킹
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int n, m;
static int [][] board;
static int total = 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());
board = new int[n][m];
List<CCTV> cctv = new ArrayList<>();
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) { // CCTV를 찾았을 때
cctv.add(new CCTV(board[i][j], i, j));
}
}
}
dfs(0, board, cctv);
System.out.println(total);
}
public static void dfs(int depth, int[][] board, List<CCTV> cctv) {
if (depth == cctv.size()) { // cctv 모든 부분을 돌았을 때
total = Math.min(total, count(board));
return;
}
int type = cctv.get(depth).type;
int x = cctv.get(depth).x;
int y = cctv.get(depth).y;
int [][] temp;
if (type == 1) {
temp = copy(board);
checkRight(temp, x, y);
dfs(depth + 1, temp, cctv);
temp = copy(board);
checkLeft(temp, x, y);
dfs(depth + 1, temp, cctv);
temp = copy(board);
checkUp(temp, x, y);
dfs(depth + 1, temp, cctv);
temp = copy(board);
checkDown(temp, x, y);
dfs(depth + 1, temp, cctv);
}
else if (type == 2) {
temp = copy(board);
checkLeft(temp, x, y);
checkRight(temp, x, y);
dfs(depth + 1, temp, cctv);
temp = copy(board);
checkUp(temp, x, y);
checkDown(temp, x, y);
dfs(depth + 1, temp, cctv);
}
else if (type == 3) {
temp = copy(board);
checkUp(temp, x, y);
checkRight(temp, x, y);
dfs(depth + 1, temp, cctv);
temp = copy(board);
checkRight(temp, x, y);
checkDown(temp, x, y);
dfs(depth + 1, temp, cctv);
temp = copy(board);
checkDown(temp, x, y);
checkLeft(temp, x, y);
dfs(depth + 1, temp, cctv);
temp = copy(board);
checkLeft(temp, x, y);
checkUp(temp, x, y);
dfs(depth + 1, temp, cctv);
}
else if (type == 4) {
temp = copy(board);
checkLeft(temp, x, y);
checkUp(temp, x, y);
checkRight(temp, x, y);
dfs(depth + 1, temp, cctv);
temp = copy(board);
checkUp(temp, x, y);
checkRight(temp, x, y);
checkDown(temp, x, y);
dfs(depth + 1, temp, cctv);
temp = copy(board);
checkRight(temp, x, y);
checkDown(temp, x, y);
checkLeft(temp, x, y);
dfs(depth + 1, temp, cctv);
temp = copy(board);
checkDown(temp, x, y);
checkLeft(temp, x, y);
checkUp(temp, x, y);
dfs(depth + 1, temp, cctv);
}
else if (type == 5) {
temp = copy(board);
checkUp(temp, x, y);
checkRight(temp, x, y);
checkDown(temp, x, y);
checkLeft(temp, x, y);
dfs(depth + 1, temp, cctv);
}
}
public static void checkRight(int [][] temp, int x, int y) {
for(int i = y + 1; i < m; i++) {
if (temp[x][i] == 6) return; // 벽이 있는 경우 지나갈 수 없음. -> continue로 착각
if (temp[x][i] == 0) temp[x][i] = -1;
}
}
public static void checkLeft(int [][] temp, int x, int y) {
for(int i = y - 1; i >= 0; i--) { // -> i 대신 y넣어서 실수...
if (temp[x][i] == 6) return; // 벽이 있는 경우 지나갈 수 없음.
if (temp[x][i] == 0) temp[x][i] = -1;
}
}
public static void checkUp(int [][] temp, int x, int y) {
for(int i = x - 1; i >= 0; i--) {
if (temp[i][y] == 6) return;
if (temp[i][y] == 0) temp[i][y] = -1;
}
}
public static void checkDown(int [][] temp, int x, int y) {
for(int i = x + 1; i < n; i++) {
if (temp[i][y] == 6) return;
if (temp[i][y] == 0) temp[i][y] = -1;
}
}
public static int[][] copy(int [][] board) {
int [][] temp = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
temp[i][j] = board[i][j];
}
}
return temp;
}
public static int count(int [][] temp) {
int count = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if (temp[i][j] == 0) count++;
}
}
return count;
}
static class CCTV {
int type;
int x;
int y;
CCTV(int type, int x, int y) {
this.type = type;
this.x = x;
this.y = y;
}
}
}
회고
각 CCTV가 볼 수 있는 방향의 최댓값은 4이고, CCTV의 최대 개수는 8개 이므로 최악의 케이스인 경우 4^8 = 65536 가짓 수가 나온다.
CCTV의 정보들을 어떻게 저장할 것인가?
- CCTV 클래스를 만들어서 타입과, 좌표 정보를 저장
각 CCTV가 감시하는 경우는 어떻게 되는가?
1번 같은 경우 모든 방향으로 4번 동작을 수행하고, 2번은 좌우 / 상하 2번, 3번은 4번, 4번도 4번, 그리고 마지막 5번은 1번만 동작을 수행하게 된다. 각 방향으로 돌면서 영역 표시를 하고, 모든 방향으로 돌았을 때는 다음 재귀함수를 호출한다.
depth == cctv.size() 처럼 모든 종류의 cctv에 대해 탐색이 마무리 된 경우, 리턴하여 다시 다음 방향을 돈다.
배열 복사는 어떻게?
int [][] temp = new int[n][m];
public static void copy(int [][] temp) {
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
temp[i][j] = board[i][j];
}
}
}
...
copy(temp);
checkRight(temp, x, y);
dfs(depth + 1, board, cctv);
기존에는 이런 식으로 배열 복사를 진행했었다. 하지만, 이런식으로 풀이를 진행하면 temp 배열을 초기화하지 않기 때문에 이전 상태가 남아있어서 문제가 된다. 결국 재사용이 문제인 것이다!
int[][] temp = copy(board);
checkRight(temp, x, y);
dfs(depth + 1, temp, cctv);
그래서 이렇게 매번 temp 배열을 초기화 해줘야 원하는 답을 구할 수 있다.
처음에 CCTV 정보를 어떻게 저장할 것인지, 백트래킹은 어떻게 돌려줄지 감이 안왔지만 풀이를 보다보니 이해가 어느정도 됐다.
이번 문제에서 배워야 될 부분은 CCTV 클래스를 선언해서 더 간편하게 정보를 저장하는 것과, 주어진 요구사항에 맞게 좌,우,상,하를 체크하는 클래스들을 만들어 잘게 쪼개 생각하는 능력이 필요할 것 같다.
'Algorithm > 백준' 카테고리의 다른 글
[백준] Silver II. 연결 요소의 개수 (0) | 2024.06.06 |
---|---|
[백준] Level IV. 빙산 (0) | 2024.06.03 |
[백준] Gold IV. 연구소 (0) | 2024.05.21 |
N과 M 문제들 다시 풀어보기 (0) | 2024.05.14 |
[백준] Silver 1. 스타트와 링크 (0) | 2024.05.13 |