[백준 15683번][Java] 감시 - 극한의 구현, 완전 탐색

www.acmicpc.net/problem/15683

15683번: 감시

 

완전 탐색, DFS를 이용하면 풀 수 있는 문제다. 문제 자체의 알고리즘 난이도는 높지 않다. 하지만 한참 고민했던 문제다.

 

문제에서 cctv는 5가지 타입이 존재하고 타입별로 가능한 탐색 방향이 존재한다. 이를 단순하게 구현하려면 배열에 5가지 타입별로 각자 방향을 일일이 저장해두고 그대로 이용할 수도 있겠지만... 지저분해지는 코드가 눈에 선했기 때문에

이를 어떻게 구현할지 꽤 오랜 시간동안 생각했다.

(그래도 막상 이 문제를 테스트에서 만난다면 노가다로 풀 것 같다)

 

해결 방법은 CCTV 객체에 Type이라는 멤버 변수를 추가하고 Type 클래스에 각 타입에 다른 Direction 열거형 클래스를 이용했다. 

 

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

/*
백준 15683번 감시
https://www.acmicpc.net/problem/15683
 */
public class Main {
    static int R,C;

    //dr, dc는 반시계 방향 순으로 나열되어 있음. 0 : 위쪽
    static Point[] dPoint = {
            Point.create(-1,0),
            Point.create(0,-1),
            Point.create(1,0),
            Point.create(0,1)
    };

    public static void main(String[] args) throws IOException {
        InputReader reader = new InputReader();
//        InputReader reader = new InputReader("testcase.txt");
        StringTokenizer st = new StringTokenizer(reader.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        int[][] room = new int[R][C];

        List<CCTV> cctvs = new ArrayList<>();
        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(reader.readLine());
            for (int j = 0; j < C; j++) {
                room[i][j] = Integer.parseInt(st.nextToken());
                if(room[i][j] > 0 && room[i][j] < 6) cctvs.add(new CCTV(Point.create(i,j), new Type(room[i][j])));
            }
        }

        int ret = findMinimumInvisibleArea(0, cctvs, room);
        System.out.println(ret);
    }

    private static int findMinimumInvisibleArea(int index, List<CCTV> cctvs, int[][] room) {
        if(index == cctvs.size()) {
            return countInvisibleArea(room);
        }

        //room 복사
        int[][] copiedRoom = new int[room.length][room[0].length];
        copy(room, copiedRoom);

        CCTV cctv = cctvs.get(index);
        Point cctvPos = cctv.point;
        Direction direction = cctv.type.direction;
        
        int ret = Integer.MAX_VALUE;
        for (int i = 0; i < direction.cycleNum; i++) {
            for (int j = 0; j < direction.directionPoints.length; j++) {
                Point dP = dPoint[direction.directionPoints[j]];
                scan(cctvPos.row, cctvPos.col, dP.row, dP.col, room);
            }
            direction.rotate();
            ret = Math.min(findMinimumInvisibleArea(index+1, cctvs, room), ret);
            
            //room 복원
            copy(copiedRoom, room);
        }
        return ret;
    }

    private static void copy(int[][] ori, int[][] target) {
        for (int i = 0; i < ori.length; i++) {
            for (int j = 0; j < ori[i].length; j++) {
                target[i][j] = ori[i][j];
            }
        }
    }

    private static int countInvisibleArea(int[][] room) {
        int cnt = 0;
        for (int i = 0; i < room.length; i++) {
            for (int j = 0; j < room[i].length; j++) {
                if(room[i][j] == 0) cnt++;
            }
        }
        return cnt;
    }

    private static void scan(int row, int col,
                             int dr, int dc, int[][] room) {
        while(true) {
            int nextRow = row+dr; int nextCol = col+dc;
            if(!isRange(nextRow, nextCol) || room[nextRow][nextCol] == 6) break;
            room[nextRow][nextCol] = -1;
            row = nextRow; col = nextCol;
        }
    }

    private static boolean isRange(int r, int c) {
        if(r < 0 || r >= R || c < 0 || c >= C) return false;
        return true;
    }
}

class CCTV {
    Type type;
    Point point;
    public CCTV(Point point, Type type) {
        this.point = point;
        this.type = type;
    }
}

class Point {
    int row, col;
    private Point(int row, int col) {
        this.row = row;
        this.col = col;
    }
    public static Point create(int row, int col) {
        return new Point(row, col);
    }
}

class Type {
    int typeId;
    Direction direction;
    public Type(int typeId) {
        this.typeId = typeId;
        this.direction = Direction.byType(typeId);
    }
}

enum Direction {
    TYPE1(1), TYPE2(2),TYPE3(3), TYPE4(4), TYPE5(5);
    int type, cycleNum;
    int[] directionPoints;

    private int[][] firstDirByType = {
            {0},
            {1, 3},
            {0, 1},
            {0, 1, 2},
            {0, 1, 2, 3}
    };
    private int[] dirSizeArr = {4,2,4,4,1};
    Direction(int type) {
        this.type = type;
        this.directionPoints = firstDirByType[type-1];
        this.cycleNum = dirSizeArr[type-1];
    }

    public void rotate() {
        for (int i = 0; i < directionPoints.length; i++) {
            directionPoints[i] = (directionPoints[i]+1)%4;
        }
    }

    public static Direction byType(int type) {
        if(type == 1) return Direction.TYPE1;
        if(type == 2) return Direction.TYPE2;
        if(type == 3) return Direction.TYPE3;
        if(type == 4) return Direction.TYPE4;
        if(type == 5) return Direction.TYPE5;
        throw new IllegalArgumentException("잘못된 타입입니다.");
    }
}

class InputReader {
    private BufferedReader br;

    public InputReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    public InputReader(String filepath) {
        try {
            br = new BufferedReader(new FileReader(filepath));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    public List<Character> readLineIntoCharList() throws IOException {
        List<Character> l = new ArrayList<>();
        while(true) {
            int readVal = br.read();
            if(readVal == '\n' || readVal == -1) break;
            l.add((char)readVal);
        }
        return l;
    }

    public boolean ready() throws IOException {
        return br.ready();
    }

    public String readLine() throws IOException {
        return br.readLine();
    }
    public int readInt() throws IOException {
        return Integer.parseInt(readLine());
    }
    public Long readLong() throws IOException {
        return Long.parseLong(readLine());
    }
}