[백준 15683] Java - 감시, 골드3, 시뮬레이션

1. 문제

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

백준 15683 감시 - 시뮬레이션, 골드3 문제

 

 

2. 접근 방법

n,m,k 최대 숫자가 정해져 있고 작기때문에 시간복잡도로 생각했을때 모든 case를 봐야한다고 생각했다

바킹독한테(알고리즘 강의 블로그에 올리시는분) 배운대로 

000, 001, 003 .... 322,323  등 모든 조합이 필요한데, 순조부로 풀 수도 있지만 4진법을 응용해서 풀었다

(나는 순조부를 맨날 까먹기때문... ^^)

 

도움 진짜 많이됨 이거 꼭보세요

https://blog.encrypted.gg/948

[실전 알고리즘] 0x0D강 - 시뮬레이션

 

4진법으로 얻은 숫자를 다시 한개씩 뜯어보면서 모든 방향을 계산해준다.

한방향, 두방향, 3방향 모든 방향등을 감시하고 감시한 숫자는 모두 7로 바꿔준다 (확인했다는 의미)

그리고 Math.min() 함수를 이용해서 최소 사각지대를 찾는다

 

 

 

3. 코드

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

//최소 사각지대 수 찾기
public class Main {
    static int n,m; //map 가로,세로
    static int k; //cctv 갯수
    static int[][] cctv;
    static int tc=1;
    static int tmpMin;
    static int min=100;
    static int[][] map;
    static int[][] cpMap;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -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];

        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) k++;
            }
        }
        cctv = new int[k][2];

        int idx=0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++) {
                if(map[i][j] >= 1 && map[i][j]<=5) {
                    cctv[idx][0] = i;
                    cctv[idx][1] = j;
                    idx++;
                }
            }
        }

        cpMap = new int[n][m];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++) {
                cpMap[i][j] = map[i][j] ; // 앞으로 사용할 복사 맵
            }
        }

        //감시 시작
        for(int i=0; i<k; i++){
            tc = tc * 4;
        }

        for(int i=0; i<tc; i++){
            //숫자에서 가져오기
            int nowN = i;

            for(int j=0; j<k; j++){
                int x = cctv[j][0];
                int y = cctv[j][1];

                int c = nowN % 4;
                nowN = nowN / 4;

                if(cpMap[x][y]==1){
                    cam(x,y,c);
                }
                else if(cpMap[x][y]==2){
                    cam(x,y,c);
                    cam(x,y,c+2);
                }
                else if(cpMap[x][y]==3){
                    cam(x,y,c);
                    cam(x,y,c+1);
                }
                else if(cpMap[x][y]==4){
                    cam(x,y,c);
                    cam(x,y,c+1);
                    cam(x,y,c+2);
                }
                else{
                    cam(x,y,c);
                    cam(x,y,c+1);
                    cam(x,y,c+2);
                    cam(x,y,c+3);
                }

            }

            //해당 case 조사
            findBlk();
            min = Math.min(min, tmpMin);
            //System.out.println("tmp:"+tmpMin);

            //숫자 초기화
            tmpMin = 0 ;

            //맵 초기화
            for(int l=0; l<n; l++){
                for(int u=0; u<m; u++) {
                    cpMap[l][u] = map[l][u] ;
                }
            }
        }
        System.out.println(min);

    }
    //방향이 주어졌을때 map을 물들이기
    private static void cam(int x,int y,int d) {
        d = d%4;

        while(true){
            x += dx[d];
            y += dy[d];
            if(check(x,y) || cpMap[x][y]==6) return;
            if(cpMap[x][y]!=0) continue;  //다른 cctv가 있을때 넘김
            cpMap[x][y] = 7;
        }
    }

    //범위 벗어나가면 false 리턴
    private static boolean check(int x, int y){
        return x<0||x>=n||y<0||y>=m;
    }

    //현재 사각지대 갯수 세기
    private static void findBlk() {
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
               // System.out.print(cpMap[i][j]+" ");
                if(cpMap[i][j] == 0) tmpMin++;
            }
            //System.out.println();
        }
    }

}

 

4. 얻은것

골드3 수준이긴한데 구현이 너무 까다롭고, 정신 못차리면 index에러가 잘난다.. 

이것도 디버깅 필수

 

이문제는 얻은 것이 많다

 1) check 함수 

 method로 구현해야 오류가 났을때 확인하기 편하다 

 

2) 4진법 응용

세자리, 4가지 숫자의 조합이 필요한 경우 64가지 경우가 필요하다 ( 4 * 4 * 4 = 64)

for문으로 0~64 의 숫자를 4진법으로 변환하여 숫자 하나씩 방향을 정하여 확인해준다

이때, 여러개 방향일 경우 반대방향은 +2, 직각방향일 경우 +1 씩 방향을 정해서 돌린다 

 

2진법과 같이 생각하면된다

4로 나눠서 남은수 ->첫번째 자리수 

그다음 다시 4로 나눈 몫을 다시 4로 나눔 -> 두번째 자리수 ... 이렇게