[백준] 15683번 / Java / 감시 - 완전탐색

문제 - (https://www.acmicpc.net/problem/15683)

전형적인 완전탐색 문제였다. 나는 모든 경우를 시뮬레이션 돌리는 방식으로 풀었다.

 

처음엔 재귀마다 map을 순회하면서 0과 6이 아닌 숫자를 찾으면 그 숫자를 가지고 시뮬레이션 하려고 했다.

하지만!!

그럼 반복문을 너무 자주 돌아야 해서 비효율적이라 생각했다.

그래서 먼저 cctv의 위치를 파악했다. => input값을 map에 넣을 때, 0과 6이 아닌 숫자를 cctvPos 리스트에 추가함

 

그렇다면 기저는 무엇일까?

dfs에 인자로 k를 주어 재귀를 들어갈때마다 1씩 더해준다

그리고 k값으로 cctvPos를 조회하도록 하면 모든 cctv를 경우의 수에 맞게 조회할 수 있다

따라서, k가 cctv의 갯수와 같아질 때 더이상 확인할 cctv는 없으므로 기저는 k==cctv의 갯수

 

기저에 다다랐을 때 전달받은 map에있는 0의 수를 세면 그것이 사각 지대의 수가 된다.

하지만 모든 경우에서 사각 지대의 수를 찾게 되므로 Math.min(계속 구해왔던 사각지대 수, 이번에 구한 사각지대 수)를 해주어

answer 변수에는 사각 지대의 최솟값만을 넣어준다!

 

k==cctv가 아니라면, 계속해서 cctv를 찾은 다음 사각지대를 찾아야 한다.

cctvPos의 k번째 cctv가 어떤 종류의 cctv인지 확인하고, 종류에 맞게 감시 가능 영역을 표시해가며 문제를 풀면 된다.

 

아 참고로

이런문제풀때 😎꿀팁!!
dx = {-1, 0, 1, 0};
dy = {0, 1, 0, -1};

를 만들어놓는다!!

dx, dy 잘보면 인덱스가 0~3일때 상,우,하 ,좌를 기리키게 된다

예를 들어 현재 위치가 1,1 이라고 하면

1+dx[0], 1+dy[0] = 0,1 = 현재 위치에서 바로 위를 가리킴

이거에 대한 건 따로 포스팅해서 머릿속에 박아놔야겠다

---

📌주의할 점

• answer 변수는 최솟값이어야 하므로 초기화시 0이 아니라 넣을 수 있는 최댓값으로 초기화해야 한다.
  나는 이 경우 Integer.MAX_VALUE를 사용한다.

• drawLine을 통해 감시 가능 영역을 표시할 때 주의해야 할 점은 dfs함수 내에서 전달받은 changedMap을 그대로 인자로 넘길 경우 "주소 참조"가 되버려서 하나를 바꾸면 나머지도 다 바뀌어버리는 상황이 발생한다. 따라서 deepCopy를 해주어 실수하지 않도록 한다.
• cctv는 종류별로 90도 회전할 수 있으므로 1~5번 각각 다른 경우의수를 갖는다.
  1번은 상/우/하/좌 4개
  2번은 상하/좌우 2개
  3번은 상우/우하/하좌/좌상 4개
  4번은 좌상우/상우하/우하좌/하좌상 4개
  5번은 상우하좌 1개
  

---

😅실수

• 처음에 dfs내부에서 이중for문으로 이차원배열인 map을 전부 순회해서 0,6이 아닌 숫자를 찾아가는 방식으로 구현했던 점

• 자꾸 왜 그러는지 모르겠다... dfs 내부에서 근거없이 무조건 for문을 쓰고 보려는 습관좀 버리자!!
  for문의 순회과정은 이미 dfs 자체에서 진행되고 있으므로 이중 for문이 필요한 경우가 아니라면 dfs 내부에 for문이 있을 필요가 없다!! 앞으로 dfs의 기저를 만들고 나서 기저가 아닐 경우를 짤 땐 항상 반복이 어떻게 이루어지는지 손으로 그린 다음에 하자

오늘의 범인

 

---

코드를 보려면 '더보기' 클릭

 

/**
 * 1시간 15분 - 시간초과
 * 1시간 30분 - 정답!
 */
public class Surveillance {
    static int n;
    static int m;
    static int[][] map;
    static int cctvCnt = 0;
    static ArrayList<int[]> cctvPos;
    static int[] dx = {-1, 0, 1, 0};  // dx dy 90도 회전 -> 상 우 하 좌
    static int[] dy = {0, 1, 0, -1};
    static int answer = Integer.MAX_VALUE; /* 최솟값을 구해야 하므로 최댓값으로 초기화 */

    static int stoi(String str) {
        return Integer.parseInt(str);
    }

    // 깊은복사
    static int[][] deepCopy(int[][] targetMap) {
        int[][] res = new int[n][m];
        for (int i = 0; i < targetMap.length; i++)
            System.arraycopy(targetMap[i], 0, res[i], 0, targetMap[0].length);
        return res;
    }

    /**
     * 감시 가능 영역 표시하기
     * @param x cctv x좌표
     * @param y cctv y좌표
     * @param dir 영역을 표시할 방향 0:상,1:우,2:하,3:좌
     * @param map 영역을 표시할 map
     * @return 감시 가능 영역을 -1로 표시한 map
     */
    static int[][] drawLine(int x, int y, int dir, int[][] map) {
        int px = dx[dir];
        int py = dy[dir];

        x += px;
        y += py;
        while (x >= 0 && y >= 0 && x < n && y < m) {
            if (map[x][y] == 0) {
                map[x][y] = -1;
            } else if (map[x][y] == 6) { // 벽을 만나면 반복문 종료
                break;
            }
            x += px;
            y += py;
        }
        return map;
    }

    static void dfs(int k, int[][] changedMap) {
        if (k == cctvCnt) {
            // 0의 갯수를 센다
            int ans = 0;
            for (int[] m : changedMap) {
                for (int _m : m) {
                    if (_m == 0) ans++;
                }
            }
            answer = Math.min(answer, ans);
            return;
        }

        /* 여기에 for문이 있으면 안되지..
        * 왜? 이미 dfs로 진입해 온 지금의 시점에서 더 반복할건 없으니까
        * 단지 감시 가능 영역을 표시하는 작업만 하면 됨 */
        //for (int p = lastPos; p < cctvPos.size(); p++) {
        int[] cPos = cctvPos.get(k);
        int i = cPos[0];
        int j = cPos[1];

        switch (changedMap[i][j]) {
            case 1:
                dfs(k + 1, drawLine(i, j, 0, deepCopy(changedMap)));
                dfs(k + 1, drawLine(i, j, 1, deepCopy(changedMap)));
                dfs(k + 1, drawLine(i, j, 2, deepCopy(changedMap)));
                dfs(k + 1, drawLine(i, j, 3, deepCopy(changedMap)));
                break;
            case 2:
                int[][] upDownMap = deepCopy(changedMap);
                drawLine(i, j, 0, upDownMap);
                drawLine(i, j, 2, upDownMap);
                dfs(k + 1, upDownMap);

                int[][] leftRightMap = deepCopy(changedMap);
                drawLine(i, j, 1, leftRightMap);
                drawLine(i, j, 3, leftRightMap);
                dfs(k + 1, leftRightMap);
                break;
            case 3:
                int[][] upRight = deepCopy(changedMap);
                drawLine(i, j, 0, upRight);
                drawLine(i, j, 1, upRight);
                dfs(k + 1, upRight);

                int[][] rightDown = deepCopy(changedMap);
                drawLine(i, j, 1, rightDown);
                drawLine(i, j, 2, rightDown);
                dfs(k + 1, rightDown);

                int[][] leftDown = deepCopy(changedMap);
                drawLine(i, j, 3, leftDown);
                drawLine(i, j, 2, leftDown);
                dfs(k + 1, leftDown);

                int[][] leftUp = deepCopy(changedMap);
                drawLine(i, j, 3, leftUp);
                drawLine(i, j, 0, leftUp);
                dfs(k + 1, leftUp);
                break;
            case 4:
                int[][] lur = deepCopy(changedMap);
                drawLine(i, j, 3, lur);
                drawLine(i, j, 0, lur);
                drawLine(i, j, 1, lur);
                dfs(k + 1, lur);

                int[][] urd = deepCopy(changedMap);
                drawLine(i, j, 0, urd);
                drawLine(i, j, 1, urd);
                drawLine(i, j, 2, urd);
                dfs(k + 1, urd);

                int[][] rdl = deepCopy(changedMap);
                drawLine(i, j, 1, rdl);
                drawLine(i, j, 2, rdl);
                drawLine(i, j, 3, rdl);
                dfs(k + 1, rdl);

                int[][] dlu = deepCopy(changedMap);
                drawLine(i, j, 2, dlu);
                drawLine(i, j, 3, dlu);
                drawLine(i, j, 0, dlu);
                dfs(k + 1, dlu);
                break;
            case 5:
                int[][] urdl = deepCopy(changedMap);
                drawLine(i, j, 0, urdl);
                drawLine(i, j, 1, urdl);
                drawLine(i, j, 2, urdl);
                drawLine(i, j, 3, urdl);
                dfs(k + 1, urdl);
                break;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
        map = new int[n][m];
        cctvPos = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = stoi(st.nextToken());
                if (map[i][j] != 0 && map[i][j] != 6) {
                    cctvCnt++;
                    cctvPos.add(new int[]{i, j});
                }
            }
        }

        dfs(0, map);
        System.out.println(answer);
    }
}