https://www.acmicpc.net/problem/15683
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
코드설명
Brute Force(완전탐색) + 구현(Implementation) + Simulation(시뮬레이션) 문제입니다.
처음 코드 작성시 놓쳤었던점은, CCTV를 두는 순서는 중요하지 않다는 것 입니다.
처음에는 CCTV를 두는 순서를 고려하는 방향으로 브루트포스를 진행하는 바람에 시간초과가 발생했습니다.
해당 문제코드를 확인해보겠습니다.
아래 코드에서 cctvArr.size() 만큼, 즉 모든 존재하는 CCTV를 순서대로 진행하는 반복문을 삭제합니다.
대신에, 현재 CCTV를 기준으로 모든 방향으로 작동시킵니다.
아래 코드에서 가장 바깥에서 CCTV Type을 도는 코드를 삭제하고, 현재 CCTV를 기준으로만 작동하게 합니다.
만약, CCTV를 이미 두었을때 다른 CCTV가 해당 위치를 지나가지 못하게 문제가 작성되었다면, 제가 작성한 코드가 맞았을 것 입니다.
CCTV를 두는 순서를 고려한 코드
for(int i=0;i<cctvArr.size();i++) {
Node temp = cctvArr.get(i);
int r = temp.r;
int c = temp.c;
int type = map[temp.r][temp.c] - 1;
if(visited[i] == false) {
visited[i] = true;
//가지고 있는 방향으로.
for(int dir = 0; dir < CCTV[type].length; dir++) {
조합코드
Node temp = cctvArr.get(cctvCnt);
int r = temp.r;
int c = temp.c;
int type = map[temp.r][temp.c] - 1;
if(visited[cctvCnt] == false) {
visited[cctvCnt] = true;
//가지고 있는 방향으로.
for(int dir = 0; dir < CCTV[type].length; dir++) {
위의 로직을 수정하면 불필요 연산이 제거되어 시간초과가 해결됩니다.
또한 문제에서 놓쳤었던점은, CCTV는 CCTV를 통과할 수 있다입니다.
즉, CCTV의 현재 종류를 놓치지 않기 위해 아래와 같이 따로 표시합니다.
문제에서는 '#'으로 표현했듯이 다른 숫자로 표현합니다.
public static int CCTVWATCH = 99;
코드
CCTV를 두는 순서에 상관없이 모든 방향을 브루트포스합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N, M;
public static int[][] map;
public static ArrayList<Node> cctvArr;
public static boolean[] visited;
//각 CCTV에 해당하는 방향을 방향으로써 표현을 한다.
//[CCTV Type:5][회전할 수 있는 횟수][화살표 개수][2]
public static int[][][][] CCTV = new int[][][][] {
{ //1번째 CCTV - 방향은 4가지 - 화살표 개수 1개
{
{0, 1}
},
{
{1, 0}
},
{
{-1, 0}
},
{
{0, -1}
}
},
{
{
{0, 1}, {0, -1}
},
{
{1, 0}, {-1, 0}
}
},
{
{
{-1, 0}, {0, 1}
},
{
{0, 1}, {1, 0}
},
{
{1, 0}, {0, -1}
},
{
{0, -1}, {-1, 0}
}
},
{
{
{0, -1}, {-1, 0}, {0, 1}
},
{
{-1, 0}, {0, 1}, {1, 0}
},
{
{0, 1}, {1, 0}, {0, -1}
},
{
{1, 0}, {0, -1}, {-1, 0}
}
},
{
{
{-1, 0}, {0, 1}, {1, 0}, {0, -1}
}
}
};
public static int answer = Integer.MAX_VALUE;
public static int CANWATCH = -1;
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());
map = new int[N][M];
cctvArr = new ArrayList<Node>();
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<M;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j] >= 1 && map[i][j] <=5) {
cctvArr.add(new Node(i, j));
}
}
}
visited = new boolean[cctvArr.size()];
simulate(0);
System.out.println(answer);
}
public static void simulate(int cctvCnt) {
if(cctvCnt == cctvArr.size()) {
int cnt = N*M;
//System.out.println("================/======");
//안전지대 개수를 셀것 입니다.
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
//System.out.print(map[i][j]);
if((map[i][j] >= 1 && map[i][j] <= 6) || map[i][j] == CANWATCH) {
cnt -= 1;
}
}
//System.out.println();
}
answer = Math.min(answer, cnt);
return ;
}
int[][] storeMap = new int[N][M];
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
storeMap[i][j] = map[i][j];
}
}
Node temp = cctvArr.get(cctvCnt);
int r = temp.r;
int c = temp.c;
int type = map[temp.r][temp.c] - 1;
if(visited[cctvCnt] == false) {
visited[cctvCnt] = true;
//가지고 있는 방향으로.
for(int dir = 0; dir < CCTV[type].length; dir++) {
for(int way = 0; way < CCTV[type][dir].length; way++) {
int dr = CCTV[type][dir][way][0];
int dc = CCTV[type][dir][way][1];
int nr = r;
int nc = c;
while(true) {
nr = nr + dr;
nc = nc + dc;
if(nr < 0 || nr >= N || nc < 0 || nc >= M) break;
if(map[nr][nc] == 6) break;
if(map[nr][nc] >=1 && map[nr][nc] <= 5) continue;
map[nr][nc] = CANWATCH;
}
}
simulate(cctvCnt + 1);
//원상복구시키고 다른 방향을 돌면서 다시 작업합니다.
for(int row=0;row<N;row++) {
for(int col=0;col<M;col++) {
map[row][col] = storeMap[row][col];
}
}
}
visited[cctvCnt] = false;
}
}
}
class Node{
int r;
int c;
public Node(int r, int c) {
this.r = r;
this.c = c;
}
}
다르게 통과한 코드입니다.
Node 를 사용하면 더 깔끔하게 풀 수 있습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static int N, M, K;
//[5][회전종류][화살표개수][2]
public static int[][][][] cctv =
{
{
{{0,1}},
{{1,0}},
{{0,-1}},
{{-1,0}}
},
{
{{0,-1},{0,1}},
{{-1,0},{1,0}}
},
{
{{-1,0},{0,1}},
{{0,1},{1,0}},
{{1,0},{0,-1}},
{{0,-1},{-1,0}}
},
{
{{0,-1},{-1,0},{0,1}},
{{-1,0},{0,1},{1,0}},
{{0,1},{1,0},{0,-1}},
{{1,0},{0,-1},{-1,0}}
},
{
{{0,1},{1,0},{0,-1},{-1,0}}
}
};
public static int answer = 0;
public static int CCTVWATCH = 99;
public static int[][] map;
public static ArrayList<int[]> cctvArr = new ArrayList<>();
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());
map = new int[N][M];
answer = N*M + 1;
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<M;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j] >= 1 && map[i][j] <= 5) {
cctvArr.add(new int[] {i, j});
}
}
}
simulate(0);
System.out.println(answer);
}
public static void simulate(int level) {
if(level == cctvArr.size()) {
//사각지대의 최소크기를 구한다.
answer = Math.min(answer, getCCTVSafeArea());
return ;
}
int[][] mapTemp = new int[N][M];
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
mapTemp[i][j] = map[i][j];
}
}
// [5][회전종류][화살표개수][2]
int cctvKind = map[cctvArr.get(level)[0]][cctvArr.get(level)[1]] - 1;
for(int dir = 0; dir<cctv[cctvKind].length; dir++) {
for(int i = 0; i < cctv[cctvKind][dir].length; i++) {
//해당 모양의 화살표를 쭉 연결한다.
seeCCTV(cctvArr.get(level)[0], cctvArr.get(level)[1], cctv[cctvKind][dir][i]);
}
simulate(level + 1);
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
map[i][j] = mapTemp[i][j];
}
}
}
}
public static void seeCCTV(int r, int c, int[] cctvSee) {
int nr = r;
int nc = c;
for(int move=1; ;move++) {
nr += cctvSee[0];
nc += cctvSee[1];
if(nr < 0 || nr >= N || nc < 0 || nc >= M) break;
if(map[nr][nc] == 6) break; //만약 벽이라면 중단.
if(map[nr][nc] >= 1 && map[nr][nc] <= 5) continue;
map[nr][nc] = CCTVWATCH;
}
}
public static int getCCTVSafeArea() {
int cnt = 0;
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
if(map[i][j] == 0) {
cnt += 1;
}
}
}
return cnt;
}
}
처음에 시간초과가 난 코드입니다.
CCTV를 두는 순서까지 고려했기에 그렇습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N, M;
public static int[][] map;
public static ArrayList<Node> cctvArr;
public static boolean[] visited;
//각 CCTV에 해당하는 방향을 방향으로써 표현을 한다.
//[CCTV Type:5][회전할 수 있는 횟수][화살표 개수][2]
public static int[][][][] CCTV = new int[][][][] {
{ //1번째 CCTV - 방향은 4가지 - 화살표 개수 1개
{
{0, 1}
},
{
{1, 0}
},
{
{-1, 0}
},
{
{0, -1}
}
},
{
{
{0, 1}, {0, -1}
},
{
{1, 0}, {-1, 0}
}
},
{
{
{-1, 0}, {0, 1}
},
{
{0, 1}, {1, 0}
},
{
{1, 0}, {0, -1}
},
{
{0, -1}, {-1, 0}
}
},
{
{
{0, -1}, {-1, 0}, {0, 1}
},
{
{-1, 0}, {0, 1}, {1, 0}
},
{
{0, 1}, {1, 0}, {0, -1}
},
{
{1, 0}, {0, -1}, {-1, 0}
}
},
{
{
{-1, 0}, {0, 1}, {1, 0}, {0, -1}
}
}
};
public static int answer = Integer.MAX_VALUE;
public static int CANWATCH = -1;
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());
map = new int[N][M];
cctvArr = new ArrayList<Node>();
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<M;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j] >= 1 && map[i][j] <=5) {
cctvArr.add(new Node(i, j));
}
}
}
visited = new boolean[cctvArr.size()];
simulate(0);
System.out.println(answer);
}
public static void simulate(int cctvCnt) {
if(cctvCnt == cctvArr.size()) {
int cnt = N*M;
//System.out.println("================/======");
//안전지대 개수를 셀것 입니다.
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
//System.out.print(map[i][j]);
if((map[i][j] >= 1 && map[i][j] <= 6) || map[i][j] == CANWATCH) {
cnt -= 1;
}
}
//System.out.println();
}
answer = Math.min(answer, cnt);
return ;
}
int[][] storeMap = new int[N][M];
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
storeMap[i][j] = map[i][j];
}
}
for(int i=0;i<cctvArr.size();i++) {
Node temp = cctvArr.get(i);
int r = temp.r;
int c = temp.c;
int type = map[temp.r][temp.c] - 1;
if(visited[i] == false) {
visited[i] = true;
//가지고 있는 방향으로.
for(int dir = 0; dir < CCTV[type].length; dir++) {
for(int way = 0; way < CCTV[type][dir].length; way++) {
int dr = CCTV[type][dir][way][0];
int dc = CCTV[type][dir][way][1];
int nr = r;
int nc = c;
while(true) {
nr = nr + dr;
nc = nc + dc;
if(nr < 0 || nr >= N || nc < 0 || nc >= M) break;
if(map[nr][nc] == 6) break;
if(map[nr][nc] >=1 && map[nr][nc] <= 5) continue;
map[nr][nc] = CANWATCH;
}
}
simulate(cctvCnt + 1);
//원상복구시키고 다른 방향을 돌면서 다시 작업합니다.
for(int row=0;row<N;row++) {
for(int col=0;col<M;col++) {
map[row][col] = storeMap[row][col];
}
}
}
visited[i] = false;
}
}
}
}
class Node{
int r;
int c;
public Node(int r, int c) {
this.r = r;
this.c = c;
}
}