본문 바로가기
알고리즘/DFS

[백준] 감시 / 자바

by 순원이 2024. 5. 30.

문제         

레벨: G3
알고리즘: 완전탐색 
풀이시간:  1:30
힌트 참조 유무: 무

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

1 번째 시도: 실패   



[알고리즘 선택 과정]

  • 각 cctv마다 방향 설정이 중요합니다
  • 그렇다면 각 cctv의 방향을 무슨 기준으로 놓아야 할까요
    • 주장: 각 CCTV마다 칸을 많이 차지하는 방향으로 
      • 반론:
        A가 칸이 많이 차지하는 방향, B가 칸이 많이 차지하는 방향으로 설정했는데
        A,B가 겹치는 것이 많은 상황을 가장해보자.

        (주장 답안)
        0 0 #
        0 0 2(A)
        0 0 #
        0 0 2(B)
        0 0 #

        (정답 답안)
        0 0 0
        # # 2(A)
        0 0 0
        # # 2(B)
        0 0 0   


        그래서 이 주장은 옳지 않습니다. 패스


  • 그렇다면 완전탐색으로 각 CCTV의 모든 방향마다 확인해야 할 것 같습니다. 
  • DFS 선택

 

[수도코드 ]

  • 입력을 받는다. 
  • CCTV의 위치는 리스트<Cctv>에 넣어놓는다.
  • 리스트<Cctv>를 순회하며 배열에 -1을 칠해가며 최솟값을 찾는다.

 

[알고리즘 구현의 어려움]

  • 구현하는데 어려움이 있음 
    • cctv 90 도로 돌리는 것을 어떻게 표현해야할지?

 

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

public class Main {
    static int N;
    static int M;
    static final int WALL = 6;
    static int[] xx = {-1, 0, 1, 0};
    static int[] yy = {0, 1, 0, -1};
    static int ans = Integer.MAX_VALUE;
    static ArrayList<Cctv> cctvs;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        int[][] arr = new int[N][M];
        cctvs = new ArrayList<Cctv>();

        for (int i = 0; i < N; i++) {
            String[] input2 = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(input2[j]);
                if (arr[i][j] != 0 && arr[i][j] != WALL) {
                    cctvs.add(new Cctv(j, i, arr[i][j]));
                }
            }
        }

        dfs(0, arr.clone());
        System.out.println(ans);

    }

    public static void dfs(int cur, int[][] arr) {


        if (cur == cctvs.size()) {
            System.out.println("배열: ");
            for(int i = 0; i < N; i++) {
                System.out.println();
                for(int j = 0; j < M; j++) {
                    System.out.print(arr[i][j]+ " ");
                }
            }
            System.out.println();
            int temp = countZero(arr);
            ans = Math.min(ans, temp);
            return;
        }

        Cctv cctv = cctvs.get(cur);

        for (int i = 0; i < 4; i++) {
            int[] dirs = choice(cctv.number, i);
            int[][] temparr = new int[][] {};
            for (int j = 0; j < dirs.length; j++) {
                temparr = fil(dirs[j], cctv, arr.clone());
            }
            dfs(cur + 1, temparr.clone());
        }
    }

    public static int countZero(int[][] tempArr) {
        int cnt = 0;
        for (int i = 0; i < tempArr.length; i++) {
            for (int j = 0; j < tempArr.length; j++) {
                if (tempArr[i][j] == 0)
                    cnt++;
            }
        }

        return cnt;
    }

    public static int[] choice(int cctv, int dir) {
        switch (cctv) {
            case 1 -> {
                if (dir == 0) {
                    return new int[]{0};
                } else if (dir == 1) {
                    return new int[]{1};
                } else if (dir == 2) {
                    return new int[]{2};
                } else {
                    return new int[]{3};
                }
            }
            case 2 -> {
                if (dir == 0) {
                    return new int[]{0, 2};
                } else if (dir == 1) {
                    return new int[]{1, 3};
                } else if (dir == 2) {
                    return new int[]{0, 2};
                } else {
                    return new int[]{1, 3};
                }
            }
            case 3 -> {
                if (dir == 0) {
                    return new int[]{0, 1};
                } else if (dir == 1) {
                    return new int[]{1, 2};
                } else if (dir == 2) {
                    return new int[]{2, 3};
                } else {
                    return new int[]{3, 0};
                }
            }
            case 4 -> {
                if (dir == 0) {
                    return new int[]{0, 1, 2};
                } else if (dir == 1) {
                    return new int[]{1, 2, 3};
                } else if (dir == 2) {
                    return new int[]{2, 3, 0};
                } else {
                    return new int[]{3, 0, 1};
                }
            }
            case 5 -> {
                return new int[]{0, 1, 2, 3};
            }
        }
        return new int[]{};
    }
    public static int[][] fil (int dir, Cctv cctv, int[][] tempArr){
        int x = cctv.x;
        int y = cctv.y;

        while (true) {
            x = x + xx[dir];
            y = y + yy[dir];
            if(x < 0 || x >= M || y <0 || y >= N || tempArr[y][x] != 0)
                break;
            tempArr[y][x] = -1;
        }

        return tempArr;
    }

    public static class Cctv {
        int x, y, number;

        public Cctv(int x, int y, int number) {
            this.x = x;
            this.y = y;
            this.number = number;
        }
    }
}
"C:\Program Files\Java\jdk-17\bin\java.exe" "-javaagent:C:\Program Files\JetBrains\IntelliJ IDEA 2023.1.1\lib\idea_rt.jar=2102:C:\Program Files\JetBrains\IntelliJ IDEA 2023.1.1\bin" -Dfile.encoding=UTF-8 -classpath C:\Users\User\Desktop\Java코드\java-pratice\out\production\java-pratice Main
4 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0


배열: 

0 0 0 0 0 0 
0 0 0 0 0 0 
-1 -1 1 0 6 0 
0 0 0 0 0 0 
배열: 

0 0 0 0 0 0 
0 0 0 0 0 0 
-1 -1 1 0 6 0 
0 0 -1 0 0 0 
배열: 

0 0 0 0 0 0 
0 0 0 0 0 0 
-1 -1 1 -1 6 0 
0 0 -1 0 0 0 
배열: 

0 0 -1 0 0 0 
0 0 -1 0 0 0 
-1 -1 1 -1 6 0 
0 0 -1 0 0 0 


9

Process finished with exit code 0



[실패 원인]
한 CCTV가 돌 수 있는 4가지 경우가 한 배열에 다 채워져 있습니다.  
왜 이러한 문제가 발생햤냐?? 제가 dfs코드에서 얉은 복사를 썼기 때문입니다.

얕은 복사 (Shallow Copy)

얕은 복사는 객체의 참조를 복사하는 것입니다. 즉, 새로 만든 객체는 원래 객체와 같은 메모리 주소를 참조합니다. 따라서 하나의 객체에서 변경된 사항은 다른 객체에도 영향을 미칩니다.

깊은 복사 (Deep Copy)

깊은 복사는 객체의 모든 값을 복사하여 완전히 새로운 객체를 생성하는 것입니다. 이렇게 하면 원래 객체와 새 객체가 서로 독립적으로 존재하게 됩니다.

 

for (int i = 0; i < 4; i++) {
    int[] dirs = choice(cctv.number, i);
    int[][] temparr = new int[][] {}; // 잘못된 초기화
    for (int j = 0; j < dirs.length; j++) {
        temparr = fil(dirs[j], cctv, arr);
    }
    dfs(cur + 1, temparr);
}
 

위 코드에서 temparr는 실제로 arr의 얕은 복사본으로 작동합니다. 즉, fil 함수가 temparr를 변경할 때, 이는 arr에도 영향을 미치게 됩니다. 그 결과, 하나의 CCTV가 다른 CCTV와 독립적으로 작동하지 않고, 서로 영향을 주게 됩니다.

2 번째 시도  

[해결법]

얉은 복사 - > 깊은 복사

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

public class Main {
    static final int WALL = 6;
    static int N;
    static int M;
    static int[] xx = {-1, 0, 1, 0};
    static int[] yy = {0, 1, 0, -1};
    static int ans = Integer.MAX_VALUE;
    static ArrayList<Cctv> cctvs;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        int[][] arr = new int[N][M];
        cctvs = new ArrayList<Cctv>();

        for (int i = 0; i < N; i++) {
            String[] input2 = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(input2[j]);
                if (arr[i][j] != 0 && arr[i][j] != WALL) {
                    cctvs.add(new Cctv(j, i, arr[i][j]));
                }
            }
        }

        dfs(0, arr);
        System.out.println(ans);
    }

    public static void dfs(int cur, int[][] arr) {
        if (cur == cctvs.size()) {
            int temp = countZero(arr);
            ans = Math.min(ans, temp);
            return;
        }

        Cctv cctv = cctvs.get(cur);

        for (int i = 0; i < 4; i++) {
            int[] dirs = choice(cctv.number, i);
            int[][] temparr = copyArray(arr);
            for (int j = 0; j < dirs.length; j++) {
                temparr = fil(dirs[j], cctv, temparr);
            }
//            System.out.println("배열: ");
//            printArray(temparr);
            dfs(cur + 1, temparr);
        }
    }

    public static int countZero(int[][] tempArr) {
        int cnt = 0;
        for (int i = 0; i < tempArr.length; i++) {
            for (int j = 0; j < tempArr[i].length; j++) {
                if (tempArr[i][j] == 0)
                    cnt++;
            }
        }
        return cnt;
    }

    public static int[] choice(int cctv, int dir) {
        switch (cctv) {
            case 1:
                return new int[]{dir};

            case 2:
                if (dir % 2 == 0) {
                    return new int[]{0, 2};
                } else {
                    return new int[]{1, 3};
                }

            case 3:
                return new int[]{dir, (dir + 1) % 4};

            case 4:
                return new int[]{dir, (dir + 1) % 4, (dir + 2) % 4};

            case 5:
                return new int[]{0, 1, 2, 3};
        }
        return new int[]{};
    }

    public static int[][] fil(int dir, Cctv cctv, int[][] tempArr) {
        int x = cctv.x;
        int y = cctv.y;

        while (true) {
            x = x + xx[dir];
            y = y + yy[dir];
            if (x < 0 || x >= M || y < 0 || y >= N || tempArr[y][x] == WALL)
                break;
            if (tempArr[y][x] == 0) {
                tempArr[y][x] = -1;
            }
        }

        return tempArr;
    }

    public static int[][] copyArray(int[][] arr) {
        int[][] newArray = new int[arr.length][];
        for (int i = 0; i < arr.length; i++) {
            newArray[i] = arr[i].clone();
        }
        return newArray;
    }

//    public static void printArray(int[][] arr) {
//        for (int i = 0; i < arr.length; i++) {
//            for (int j = 0; j < arr[i].length; j++) {
//                System.out.print(arr[i][j] + " ");
//            }
//            System.out.println();
//        }
//    }

    public static class Cctv {
        int x, y, number;

        public Cctv(int x, int y, int number) {
            this.x = x;
            this.y = y;
            this.number = number;
        }
    }
}
"C:\Program Files\Java\jdk-17\bin\java.exe" "-javaagent:C:\Program Files\JetBrains\IntelliJ IDEA 2023.1.1\lib\idea_rt.jar=2162:C:\Program Files\JetBrains\IntelliJ IDEA 2023.1.1\bin" -Dfile.encoding=UTF-8 -classpath C:\Users\User\Desktop\Java코드\java-pratice\out\production\java-pratice Main
4 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0
배열: 
0 0 0 0 0 0 
0 0 0 0 0 0 
-1 -1 1 0 6 0 
0 0 0 0 0 0 
배열: 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 1 0 6 0 
0 0 -1 0 0 0 
배열: 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 1 -1 6 0 
0 0 0 0 0 0 
배열: 
0 0 -1 0 0 0 
0 0 -1 0 0 0 
0 0 1 0 6 0 
0 0 0 0 0 0 
20

Process finished with exit code 0

 

 

이 문제는 완전탐색으로 분류되지만 사실상 구현에 시간이 많이 들어 구현 문제인 것 같다..

저작자표시

'알고리즘 > DFS' 카테고리의 다른 글

[백준 1967] 트리의 지름 / 자바 / DFS  (1) 2024.06.20
[백준 1987] 알파벳 / 자바 / 백트래킹  (0) 2024.06.19
[백준] 치킨배달/ 자바**  (0) 2024.05.21
[백준] 연구소/자바  (0) 2024.05.08
[백준] 트리의 지름/자바  (0) 2024.05.06

관련글

티스토리툴바