감시

https://www.acmicpc.net/problem/15683

풀이

감시카메라의 종류가 5개이고 회전이 4방향이 가능하기때문에 각 감시카메라가 볼 수 있는 방향에 대한 모든 경우의 수를 구해 사각지대를 계산하면 되는 문제이다.

1번 방법 같은 경우 감시카메라가 볼 수 있는 방향을 순열로 미리 구해두고 그 다음 사각지대를 계산했다면 2번 방법은 감시카메라를 하나 선택해서 방향을 지정하고 다음 감시카메라 방향을 선택한다.

2번 방법이 미리 순열을 구해 한번에 보는 것보다 시간도 절약되고 메모리도 절약된다.

코드

1번

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    static int n, m;
    static int[][] map;
    static int[][] copyMap;
    static ArrayList<CCTV> backup = new ArrayList<>();
    static boolean[][] visit;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] in = br.readLine().split(" ");
        n = Integer.parseInt(in[0]);
        m = Integer.parseInt(in[1]);
        map = new int[n][m];
        copyMap = new int[n][m];
        int totalArea = 0;
        String[] line;
        for (int i = 0; i < n; i++) {
            line = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(line[j]);
                if (map[i][j] == 0)
                    totalArea++;
                if (map[i][j] != 0 && map[i][j] != 6) {
                    backup.add(new CCTV(i, j, map[i][j]));
                }
            }
        }
        visit = new boolean[backup.size()][4];

        backTracking(0, 0, totalArea);

        bw.write(min + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private static void backTracking(int pos, int cnt, int total) {
        if (cnt == backup.size()) {
            check(total);
            return;
        }
        for (int i = pos; i < backup.size(); i++) {
            for (int j = 0; j < 4; j++) {
                if (!visit[i][j]) {
                    visit[i][j] = true;
                    backup.get(cnt).dir = j;
                    backTracking(i + 1, cnt + 1, total);
                    visit[i][j] = false;
                }
            }
        }
    }

    // 0 0도 1 90도 2 180도 3 270도
    private static void check(int total) {
        init();
        for (CCTV c : backup) {
            total = drawArea(c, total);
        }

        min = Math.min(total, min);
        if (min == 0) {
            System.out.println(min);
            System.exit(0);
        }
    }

    private static int drawArea(CCTV c, int total) {
        if (c.num == 1) {
            int x = c.x;
            int y = c.y;
            if (c.dir == 0) {
                // 우
                total = drawRight(x, y, total);
            } else if (c.dir == 1) {
                // 하
                total = drawDown(x, y, total);
            } else if (c.dir == 2) {
                // 좌
                total = drawLeft(x, y, total);
            } else if (c.dir == 3) {
                // 상
                total = drawUp(x, y, total);
            }
        }
        // 2
        else if (c.num == 2) {
            int x = c.x;
            int y = c.y;
            if (c.dir == 0 || c.dir == 2) {
                // 좌
                total = drawLeft(x, y, total);
                // 우
                total = drawRight(x, y, total);
            } else if (c.dir == 1 || c.dir == 3) {
                // 상
                total = drawUp(x, y, total);
                // 하
                total = drawDown(x, y, total);
            }
        }
        // 3
        else if (c.num == 3) {
            int x = c.x;
            int y = c.y;
            if (c.dir == 0) {
                // 상
                total = drawUp(x, y, total);
                // 우
                total = drawRight(x, y, total);
            } else if (c.dir == 1) {
                // 우
                total = drawRight(x, y, total);
                // 하
                total = drawDown(x, y, total);
            } else if (c.dir == 2) {
                // 하
                total = drawDown(x, y, total);
                // 좌
                total = drawLeft(x, y, total);
            } else if (c.dir == 3) {
                // 상
                total = drawUp(x, y, total);
                // 좌
                total = drawLeft(x, y, total);
            }
        }
        // 4
        else if (c.num == 4) {
            if (c.dir == 0 || c.dir == 2) {
                int x = c.x;
                int y = c.y;

                if (c.dir == 0)
                    // 상
                    total = drawUp(x, y, total);
                else
                    // 하
                    total = drawDown(x, y, total);

                // 좌
                total = drawLeft(x, y, total);
                // 우
                total = drawRight(x, y, total);
            }
            //
            else if (c.dir == 1 || c.dir == 3) {
                int x = c.x;
                int y = c.y;
                // 상
                total = drawUp(x, y, total);
                // 하
                total = drawDown(x, y, total);
                if (c.dir == 1)
                    // 우
                    total = drawRight(x, y, total);
                else
                    // 좌
                    total = drawLeft(x, y, total);
            }
        }
        // 5
        else if (c.num == 5) {
            int x = c.x;
            int y = c.y;
            // 상
            total = drawUp(x, y, total);
            // 좌
            total = drawLeft(x, y, total);
            // 하
            total = drawDown(x, y, total);
            // 우
            total = drawRight(x, y, total);
        }
        return total;
    }

    private static void init() {
        for (int i = 0; i < n; i++) {
            copyMap[i] = Arrays.copyOf(map[i], m);
        }
    }

    private static int drawUp(int x, int y, int total) {
        // 상
        for (int i = x - 1; i >= 0; i--) {
            if (copyMap[i][y] != 6) {
                if (copyMap[i][y] == 0) {
                    copyMap[i][y] = -1;
                    total--;
                }
            } else
                break;
        }
        return total;
    }

    private static int drawLeft(int x, int y, int total) {
        // 좌
        for (int i = y - 1; i >= 0; i--) {
            if (copyMap[x][i] != 6) {
                if (copyMap[x][i] == 0) {
                    copyMap[x][i] = -1;
                    total--;
                }
            } else
                break;
        }
        return total;
    }

    private static int drawDown(int x, int y, int total) {
        // 하
        for (int i = x + 1; i < n; i++) {
            if (copyMap[i][y] != 6) {
                if (copyMap[i][y] == 0) {
                    copyMap[i][y] = -1;
                    total--;
                }
            } else
                break;
        }
        return total;
    }

    private static int drawRight(int x, int y, int total) {
        // 우
        for (int i = y + 1; i < m; i++) {
            if (copyMap[x][i] != 6) {
                if (copyMap[x][i] == 0) {
                    copyMap[x][i] = -1;
                    total--;
                }
            } else
                break;
        }
        return total;
    }
}

class CCTV implements Comparable<CCTV> {
    int x;
    int y;
    int num;
    int dir;

    public CCTV(int x, int y, int num) {
        this.x = x;
        this.y = y;
        this.num = num;
    }

    @Override
    public int compareTo(CCTV o) {
        return -1 * Integer.compare(this.num, o.num);
    }
}

2번

import java.io.*;
import java.util.ArrayList;

public class Test1 {
    static int n, m;
    static int[][] copyMap;
    static ArrayList<CCTV> backup = new ArrayList<>();
    static int min = Integer.MAX_VALUE;
    static int totalCnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] in = br.readLine().split(" ");
        n = Integer.parseInt(in[0]);
        m = Integer.parseInt(in[1]);
        copyMap = new int[n][m];
        int totalArea = 0;
        String[] line;
        for (int i = 0; i < n; i++) {
            line = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                int num = Integer.parseInt(line[j]);
                if (num == 6)
                    copyMap[i][j] = Integer.parseInt(line[j]);
                if (num == 0) {
                    totalArea++;
                    totalCnt++;
                }
                if (num != 0 && num != 6) {
                    copyMap[i][j] = -100;
                    backup.add(new CCTV(i, j, num));
                }
            }
        }

        start(0, totalArea);
        bw.write(min + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private static int drawArea(CCTV c, int total) {
        if (c.num == 1) {
            int x = c.x;
            int y = c.y;
            if (c.dir == 0) {
                // 우
                total = drawRight(x, y, total);
            } else if (c.dir == 1) {
                // 하
                total = drawDown(x, y, total);
            } else if (c.dir == 2) {
                // 좌
                total = drawLeft(x, y, total);
            } else if (c.dir == 3) {
                // 상
                total = drawUp(x, y, total);
            }
        }
        // 2
        else if (c.num == 2) {
            int x = c.x;
            int y = c.y;
            if (c.dir == 0 || c.dir == 2) {
                // 좌
                total = drawLeft(x, y, total);
                // 우
                total = drawRight(x, y, total);
            } else if (c.dir == 1 || c.dir == 3) {
                // 상
                total = drawUp(x, y, total);
                // 하
                total = drawDown(x, y, total);
            }
        }
        // 3
        else if (c.num == 3) {
            int x = c.x;
            int y = c.y;
            if (c.dir == 0) {
                // 상
                total = drawUp(x, y, total);
                // 우
                total = drawRight(x, y, total);
            } else if (c.dir == 1) {
                // 우
                total = drawRight(x, y, total);
                // 하
                total = drawDown(x, y, total);
            } else if (c.dir == 2) {
                // 하
                total = drawDown(x, y, total);
                // 좌
                total = drawLeft(x, y, total);
            } else if (c.dir == 3) {
                // 상
                total = drawUp(x, y, total);
                // 좌
                total = drawLeft(x, y, total);
            }
        }
        // 4
        else if (c.num == 4) {
            if (c.dir == 0 || c.dir == 2) {
                int x = c.x;
                int y = c.y;

                if (c.dir == 0)
                    // 상
                    total = drawUp(x, y, total);
                else
                    // 하
                    total = drawDown(x, y, total);

                // 좌
                total = drawLeft(x, y, total);
                // 우
                total = drawRight(x, y, total);
            }
            //
            else if (c.dir == 1 || c.dir == 3) {
                int x = c.x;
                int y = c.y;
                // 상
                total = drawUp(x, y, total);
                // 하
                total = drawDown(x, y, total);
                if (c.dir == 1)
                    // 우
                    total = drawRight(x, y, total);
                else
                    // 좌
                    total = drawLeft(x, y, total);
            }
        }
        // 5
        else if (c.num == 5) {
            int x = c.x;
            int y = c.y;
            // 상
            total = drawUp(x, y, total);
            // 좌
            total = drawLeft(x, y, total);
            // 하
            total = drawDown(x, y, total);
            // 우
            total = drawRight(x, y, total);
        }
        return total;
    }

    private static int drawUp(int x, int y, int total) {
        // 상
        for (int i = x - 1; i >= 0; i--) {
            if (copyMap[i][y] != 6) {
                if (copyMap[i][y] == 0) {
                    total--;
                    totalCnt--;
                }
                copyMap[i][y]--;
            } else
                break;
        }
        return total;
    }

    private static int drawLeft(int x, int y, int total) {
        // 좌
        for (int i = y - 1; i >= 0; i--) {
            if (copyMap[x][i] != 6) {
                if (copyMap[x][i] == 0) {
                    total--;
                    totalCnt--;
                }
                copyMap[x][i]--;
            } else
                break;
        }
        return total;
    }

    private static int drawDown(int x, int y, int total) {
        // 하
        for (int i = x + 1; i < n; i++) {
            if (copyMap[i][y] != 6) {
                if (copyMap[i][y] == 0) {
                    total--;
                    totalCnt--;
                }
                copyMap[i][y]--;
            } else
                break;
        }
        return total;
    }

    private static int drawRight(int x, int y, int total) {
        // 우
        for (int i = y + 1; i < m; i++) {
            if (copyMap[x][i] != 6) {
                if (copyMap[x][i] == 0) {
                    total--;
                    totalCnt--;
                }
                copyMap[x][i]--;
            } else
                break;
        }
        return total;
    }

    private static void start(int cnt, int total) {
        if (cnt == backup.size()) {
            min = Math.min(min, totalCnt);
            return;
        }

        CCTV c = backup.get(cnt);

        for (int i = 0; i < 4; i++) {
            c.dir = i;
            total = drawArea(c, total);
            start(cnt + 1, total);
            total = eraseArea(c, total);
        }
    }

    private static int eraseArea(CCTV c, int total) {
        if (c.num == 1) {
            int x = c.x;
            int y = c.y;
            if (c.dir == 0) {
                // 우
                total = eraseRight(x, y, total);
            } else if (c.dir == 1) {
                // 하
                total = eraseDown(x, y, total);
            } else if (c.dir == 2) {
                // 좌
                total = eraseLeft(x, y, total);
            } else if (c.dir == 3) {
                // 상
                total = eraseUp(x, y, total);
            }
        }
        // 2
        else if (c.num == 2) {
            int x = c.x;
            int y = c.y;
            if (c.dir == 0 || c.dir == 2) {
                // 좌
                total = eraseLeft(x, y, total);
                // 우
                total = eraseRight(x, y, total);
            } else if (c.dir == 1 || c.dir == 3) {
                // 상
                total = eraseUp(x, y, total);
                // 하
                total = eraseDown(x, y, total);
            }
        }
        // 3
        else if (c.num == 3) {
            int x = c.x;
            int y = c.y;
            if (c.dir == 0) {
                // 상
                total = eraseUp(x, y, total);
                // 우
                total = eraseRight(x, y, total);
            } else if (c.dir == 1) {
                // 우
                total = eraseRight(x, y, total);
                // 하
                total = eraseDown(x, y, total);
            } else if (c.dir == 2) {
                // 하
                total = eraseDown(x, y, total);
                // 좌
                total = eraseLeft(x, y, total);
            } else if (c.dir == 3) {
                // 상
                total = eraseUp(x, y, total);
                // 좌
                total = eraseLeft(x, y, total);
            }
        }
        // 4
        else if (c.num == 4) {
            if (c.dir == 0 || c.dir == 2) {
                int x = c.x;
                int y = c.y;

                if (c.dir == 0)
                    // 상
                    total = eraseUp(x, y, total);
                else
                    // 하
                    total = eraseDown(x, y, total);

                // 좌
                total = eraseLeft(x, y, total);
                // 우
                total = eraseRight(x, y, total);
            }
            //
            else if (c.dir == 1 || c.dir == 3) {
                int x = c.x;
                int y = c.y;
                // 상
                total = eraseUp(x, y, total);
                // 하
                total = eraseDown(x, y, total);
                if (c.dir == 1)
                    // 우
                    total = eraseRight(x, y, total);
                else
                    // 좌
                    total = eraseLeft(x, y, total);
            }
        }
        // 5
        else if (c.num == 5) {
            int x = c.x;
            int y = c.y;
            // 상
            total = eraseUp(x, y, total);
            // 좌
            total = eraseLeft(x, y, total);
            // 하
            total = eraseDown(x, y, total);
            // 우
            total = eraseRight(x, y, total);
        }
        return total;
    }

    private static int eraseUp(int x, int y, int total) {
        // 상
        for (int i = x - 1; i >= 0; i--) {
            if (copyMap[i][y] != 6) {
                copyMap[i][y]++;
                if (copyMap[i][y] == 0) {
                    totalCnt++;
                    total++;
                }
            } else
                break;
        }
        return total;
    }

    private static int eraseLeft(int x, int y, int total) {
        // 좌
        for (int i = y - 1; i >= 0; i--) {
            if (copyMap[x][i] != 6) {
                copyMap[x][i]++;
                if (copyMap[x][i] == 0) {
                    totalCnt++;
                    total++;
                }
            } else
                break;
        }
        return total;
    }

    private static int eraseDown(int x, int y, int total) {
        // 하
        for (int i = x + 1; i < n; i++) {
            if (copyMap[i][y] != 6) {
                copyMap[i][y]++;
                if (copyMap[i][y] == 0) {
                    total++;
                    totalCnt++;
                }
            } else
                break;
        }
        return total;
    }

    private static int eraseRight(int x, int y, int total) {
        // 우
        for (int i = y + 1; i < m; i++) {
            if (copyMap[x][i] != 6) {
                copyMap[x][i]++;
                if (copyMap[x][i] == 0) {
                    total++;
                    totalCnt++;
                }
            } else
                break;
        }
        return total;
    }
}