- 생각
1. DFS로 돌리는 경우 - 1번 4개, 2번 2개, 3번 4개, 4번 4개, 5번 1개로 모든 방향으로 확인하면서 복구 시킨다.
==>> 시간초과 뜰 것 같았는데 역시 시간초과가 뜬다. 어떻게 고쳐야하지?
- 코드
정답 코드 : 똑같이 dfs로 풀고 비슷한 방식으로 풀었는데 이건 왜 빠른지 찾아보자.. 아직 이해안함
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int R, C, result, cnt, tmpResult;
static int[][] grid;
static int[][][] camPos;
static int[] camCount, camAcc;
static int[][] camDir;
static int[] dirTypes = {4, 2, 4, 4, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine().trim());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
grid = new int[R][C];
result = Integer.MAX_VALUE;
camPos = new int[5][8][2];
camDir = new int[5][8];
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 8; j++) {
camDir[i][j] = -1;
}
}
camCount = new int[5];
for (int r = 0; r < R; r++) {
st = new StringTokenizer(br.readLine().trim());
for (int c = 0; c < C; c++) {
grid[r][c] = Integer.parseInt(st.nextToken());
if(grid[r][c] == 0)
continue;
else if(grid[r][c] == 6)
continue;
else {
camPos[grid[r][c]-1][camCount[grid[r][c]-1]][0] = r;
camPos[grid[r][c]-1][camCount[grid[r][c]-1]][1] = c;
// System.out.println(r+","+c);
camCount[grid[r][c]-1] ++;
}
}
}
camAcc = new int[5];
for (int i = 0; i < 5; i++) {
camAcc[i] = camCount[i];
}
for (int i = 1; i < 5; i++) {
camAcc[i] = camAcc[i-1] + camAcc[i];
}
DFS(0);
System.out.println(result);
}
private static void DFS(int count) {
if(count == camAcc[4]) {
// for (int i = 0; i < 5; i++) {
// for (int j = 0; j < 8; j++) {
// System.out.print(camDir[i][j]+" ");
// }
// System.out.println();
// }
// System.out.println();
int[][] tmpGrid = new int[R][C];
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
tmpGrid[r][c] = grid[r][c];
}
}
tmpResult = 0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < camCount[i]; j++) {
if(i == 0) {
dirCheck(camDir[i][j], tmpGrid, camPos[i][j][0], camPos[i][j][1]);
} else if(i == 1) {
dirCheck(camDir[i][j], tmpGrid, camPos[i][j][0], camPos[i][j][1]);
dirCheck(camDir[i][j]+2, tmpGrid, camPos[i][j][0], camPos[i][j][1]);
} else if(i == 2) {
dirCheck(camDir[i][j], tmpGrid, camPos[i][j][0], camPos[i][j][1]);
dirCheck((camDir[i][j]+1)%4, tmpGrid, camPos[i][j][0], camPos[i][j][1]);
} else if(i == 3) {
dirCheck(camDir[i][j], tmpGrid, camPos[i][j][0], camPos[i][j][1]);
dirCheck((camDir[i][j]+1)%4, tmpGrid, camPos[i][j][0], camPos[i][j][1]);
dirCheck((camDir[i][j]+2)%4, tmpGrid, camPos[i][j][0], camPos[i][j][1]);
} else {
dirCheck(camDir[i][j], tmpGrid, camPos[i][j][0], camPos[i][j][1]);
dirCheck((camDir[i][j]+1)%4, tmpGrid, camPos[i][j][0], camPos[i][j][1]);
dirCheck((camDir[i][j]+2)%4, tmpGrid, camPos[i][j][0], camPos[i][j][1]);
dirCheck((camDir[i][j]+3)%4, tmpGrid, camPos[i][j][0], camPos[i][j][1]);
}
}
}
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if(tmpGrid[r][c] == 0)
tmpResult++;
}
}
if(result > tmpResult) {
result = tmpResult;
// for (int r = 0; r < R; r++) {
// for (int c = 0; c < C; c++) {
// System.out.print(tmpGrid[r][c]+" ");
// }
// System.out.println();
// }
//
// System.out.println();
//
}
return;
}
int type = -1;
int idx = -1;
// System.out.println(count);
for (int i = 0; i < 5; i++) {
if(count < camAcc[i]) {
type = i;
if(i == 0)
idx = count;
else
idx = count - camAcc[i-1];
break;
}
}
for (int i = 0; i < dirTypes[type]; i++) {
camDir[type][idx] = i;
DFS(count + 1);
}
}
private static void dirCheck(int dir, int[][] tmpGrid, int currR, int currC) {
int[] dr = {-1, 0, 1, 0};
int[] dc = {0, 1, 0, -1};
int tr = currR;
int tc = currC;
while(true) {
tr += dr[dir];
tc += dc[dir];
if(tr >= R || tc >= C || tr < 0 || tc < 0)
break;
int currVal = tmpGrid[tr][tc];
if(currVal == 6)
break;
if(currVal == 0) {
tmpGrid[tr][tc] = 9;
}
else
continue;
}
}
}
실패 코드 : 앞선 1의 시간초과뜬 코드이다. 시간을 줄일 방법이 생각이 안난다..
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, M, count, minValue;
static int[][] array;
static int[] x, y;
public static void main(String[] args) throws Exception {
SetData();
DFS(0);
System.out.println(minValue);
}
// 데이터
private static void SetData() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
count = 0; // 벽이 아닌 방향이 있는 1~5 숫자가 몇개있는지 count (basecase로 두기 위함)
array = new int[N][M];
x = new int[8];
y = new int[8];
minValue = Integer.MAX_VALUE; // 사각지대 최소 개수
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
array[i][j] = Integer.parseInt(st.nextToken());
// 미리 cctv 좌표를 저장한다.
if (array[i][j] != 0 && array[i][j] != 6) {
x[count] = i;
y[count] = j;
count++;
}
}
}
}
private static void DFS(int startIndex) {
// basecase 모든 cctv를 확인해본 결과
if (startIndex == count) {
minValue = Math.min(minValue, RemainCCTV());
return;
}
for (int i = startIndex; i < count; i++) {
if (array[x[i]][y[i]] == 1) {
CheckCCTV(x[i], y[i], startIndex, 1);
} else if (array[x[i]][y[i]] == 2) {
CheckCCTV(x[i], y[i], startIndex, 2);
} else if (array[x[i]][y[i]] == 3) {
CheckCCTV(x[i], y[i], startIndex, 3);
} else if (array[x[i]][y[i]] == 4) {
CheckCCTV(x[i], y[i], startIndex, 4);
} else if (array[x[i]][y[i]] == 5) {
CheckCCTV(x[i], y[i], startIndex, 5);
}
}
}
private static void CheckCCTV(int i, int j, int startIndex, int numberOfCCTV) {
switch (numberOfCCTV) {
case 1:
GoUp(i,j);
DFS(startIndex + 1);
GoBackUp(i,j);
GoDown(i,j);
DFS(startIndex + 1);
GoBackDown(i,j);
GoLeft(i,j);
DFS(startIndex + 1);
GoBackLeft(i,j);
GoRight(i,j);
DFS(startIndex + 1);
GoBackRight(i,j);
break;
case 2:
GoUp(i,j);
GoDown(i,j);
DFS(startIndex + 1);
GoBackUp(i,j);
GoBackDown(i,j);
GoLeft(i,j);
GoRight(i,j);
DFS(startIndex + 1);
GoBackLeft(i,j);
GoBackRight(i,j);
break;
case 3:
GoDown(i,j);
GoLeft(i,j);
DFS(startIndex + 1);
GoBackDown(i,j);
GoBackLeft(i,j);
GoUp(i,j);
GoRight(i,j);
DFS(startIndex + 1);
GoBackUp(i,j);
GoBackRight(i,j);
GoLeft(i,j);
GoUp(i,j);
DFS(startIndex + 1);
GoBackUp(i,j);
GoBackLeft(i,j);
GoRight(i,j);
GoDown(i,j);
DFS(startIndex + 1);
GoBackRight(i,j);
GoBackDown(i,j);
break;
case 4:
GoUp(i,j);
GoDown(i,j);
GoLeft(i,j);
DFS(startIndex + 1);
GoBackUp(i,j);
GoBackDown(i,j);
GoBackLeft(i,j);
GoUp(i,j);
GoDown(i,j);
GoRight(i,j);
DFS(startIndex + 1);
GoBackUp(i,j);
GoBackDown(i,j);
GoBackRight(i,j);
GoLeft(i,j);
GoRight(i,j);
GoUp(i,j);
DFS(startIndex + 1);
GoBackUp(i,j);
GoBackLeft(i,j);
GoBackRight(i,j);
GoLeft(i,j);
GoRight(i,j);
GoDown(i,j);
DFS(startIndex + 1);
GoBackLeft(i,j);
GoBackRight(i,j);
GoBackDown(i,j);
break;
case 5:
GoUp(i,j);
GoDown(i,j);
GoLeft(i,j);
GoRight(i,j);
DFS(startIndex + 1);
GoBackUp(i,j);
GoBackDown(i,j);
GoBackLeft(i,j);
GoBackRight(i,j);
break;
default:
break;
}
}
private static void GoUp(int startI, int startJ) {
for (int i = startI; i >= 0; i--) {
if (array[i][startJ] == 6)
break;
if (array[i][startJ] == 0)
array[i][startJ] = 7;
}
}
private static void GoDown(int startI, int startJ) {
for (int i = startI; i > N; i++) {
if (array[i][startJ] == 6)
break;
if (array[i][startJ] == 0)
array[i][startJ] = 7;
}
}
private static void GoLeft(int startI, int startJ) {
for (int j = startJ; j >= 0; j--) {
if (array[startI][j] == 6)
break;
if (array[startI][j] == 0)
array[startI][j] = 7;
}
}
private static void GoRight(int startI, int startJ) {
for (int j = startJ; j < M; j++) {
if (array[startI][j] == 6)
break;
if (array[startI][j] == 0)
array[startI][j] = 7;
}
}
private static void GoBackUp(int startI, int startJ) {
for (int i = startI; i >= 0; i--) {
if (array[i][startJ] == 6)
break;
if (array[i][startJ] == 7)
array[i][startJ] = 0;
}
}
private static void GoBackDown(int startI, int startJ) {
for (int i = startI; i > N; i++) {
if (array[i][startJ] == 6)
break;
if (array[i][startJ] == 7)
array[i][startJ] = 0;
}
}
private static void GoBackLeft(int startI, int startJ) {
for (int j = startJ; j >= 0; j--) {
if (array[startI][j] == 6)
break;
if (array[startI][j] == 7)
array[startI][j] = 0;
}
}
private static void GoBackRight(int startI, int startJ) {
for (int j = startJ; j < M; j++) {
if (array[startI][j] == 6)
break;
if (array[startI][j] == 7)
array[startI][j] = 0;
}
}
private static int RemainCCTV() {
int countOfCCTV = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (array[i][j] == 0)
countOfCCTV++;
}
}
return countOfCCTV;
}
}'algorithm' 카테고리의 다른 글
| [JAVA] 백준 1700번 : 멀티탭 스케줄링 (0) | 2020.11.09 |
|---|---|
| [JAVA] 백준 1202번 : 보석 도둑 (0) | 2020.11.09 |
| [JAVA] 백준 2011번 : 암호코드 (0) | 2020.11.05 |
| [JAVA] 백준 1062번 : 가르침 (0) | 2020.11.04 |
| [JAVA] 백준 1516번 : 게임 개발 (0) | 2020.11.04 |