<Algorithm> 153. 홈 방범 서비스(SWExpert)

1. 홈 방범 서비스(SWExpert)

   사용 알고리즘 : BFS, 완전탐색

• 처음에 문제를 봤을때 어려워보인다는 생각이 들었는데 잘 생각해보니 답이 풀렸다.

• 이걸 풀고 가장 속도가 낮은 풀이를 봤는데 수학적으로 접근한 것을 보고 놀라웠다... 저 경지에 이르려면 어떤 사고가 필요할까..

문제에 대한 접근&생각

1. 영역모양이 어디서 많이 본듯함 -> 세포배양문제 풀때 나옴 -> BFS가 거리에 따라 탐색하는 모양이랑 같음 -> BFS!
2. 모든 서비스 영역에 대해 홈 방법서비스 영역을 구해야함 -> 완전탐색!
3. 전체 모든 배열이 서비스 영역일 수 있음 -> k는 n보다 크게 

다른 방법 풀이

• 이 방법도 좌표를 기준으로 하지만 좌표에 대해 모든 홈의 좌표를 탐색한다.

• 수학적으로 해당 좌표에서 홈좌표를 각각 빼서 더하면 영역의 크기를 알 수 있다.

내 코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95

import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Scanner;   public class Solution {     static int n,m;     static int[][] map;     static int[][] dist;     static boolean[][] visted;     static List<Pair> list;     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int T = sc.nextInt();         /******************************          * BFS를 이용해 방법 서비스의 모든 영역이          * 되는 구간을 완전탐색을 통해 구해서          * 그 안에 들어가는 카메라의 개수를 구한다.          *******************************/         for(int t = 1; t <= T; t++) {             list = new LinkedList<>();             n = sc.nextInt();             m = sc.nextInt();             map = new int[n][n];             for(int i = 0; i < n; i++) {                 for(int j = 0; j < n; j++ ) {                     int home = sc.nextInt();                     map[i][j] = home;                 }             }                          int max = 0;             for(int k = 1; k <= n+1; k++) {                 for(int i = 0; i < n; i++) {                     for(int j = 0; j < n; j++) {                         dist = new int[n][n];                         visted = new boolean[n][n];                         count = 0;                         bfs(i, j, k);                         int cost = k*k+(k-1)*(k-1);                         int total = count*m-cost;                         //System.out.println("k : "+k+" cost : "+cost+" total : "+ total+" count : "+count);                         if(total >= 0)                              max = Math.max(max, count);                     }                 }             }                          System.out.println("#"+t+" "+max);         }     }     static int[] dx = {0,0,1,-1};     static int[] dy = {1,-1,0,0};     static int count;     private static void bfs(int x,int y,int k) {         Queue<Pair> queue = new LinkedList<>();         queue.add(new Pair(x, y));         visted[x][y] = true;         dist[x][y] = 1;         if(map[x][y]== 1) count++;                  while (!queue.isEmpty()) {             Pair start = queue.remove();             if(dist[start.x][start.y] > k) return;             //if(k == 2 && x==0 &&y==0) print();             for(int i = 0; i < 4; i++) {                 int nx = start.x + dx[i];                 int ny = start.y + dy[i];                 if(isBoundary(nx, ny)&&!visted[nx][ny]) {                     dist[nx][ny] = dist[start.x][start.y]+1;                     visted[nx][ny] = true;                     if(dist[nx][ny]<=k) {                         queue.add(new Pair(nx, ny));                         count = map[nx][ny]==1?count+1:count;                     }                 }             }         }     }          public static boolean isBoundary(int nx,int ny) {         if(nx >= 0 && ny >= 0 && nx < n && ny < n)              return true;         return false;     }     static class Pair{         int x,y;           public Pair(int x, int y) {             this.x = x;             this.y = y;         }     } }   Colored by Color Scripter

cs

 

참고 & 출처