백준 15683번 - 감시

구현 방법

문제를 분석해보면

수학적 귀납법 방식이 아닌 절차적인 방식으로 접근해야 함을 알 수 있다. CCTV 개수, 위치가 무작위이기 때문에 규칙, 점화식을 세우는 수학적 귀납법 방식의 풀이로는 해결하기 힘들다.

절차적인 방식은 순차적으로 해보는 방식으로 첫번째 CCTV 부터 마지막 CCTV 까지 하나씩 모든 경우에 대해서 해봐야 한다.

백트래킹으로 첫번째 CCTV 부터 마지막 CCTV 까지 재귀로 처리하는 것은 메모리 초과가 나올 수도 있고 구현도 어렵고, 시간도 더 오래 걸릴 수 있다.

 

첫번째 CCTV부터 마지막 CCTV까지의 방향을 하나의 상태 값을 만들 수 있다면, 재귀의 백트래킹이 아닌 방식으로 처리할 수 있다.

CCTV는 방향에 따라 위, 아래, 오른쪽, 왼쪽 을 갖는다. 이를 숫자로 표현한다면 0, 1, 2, 3 이 된다.

 

두번째 이상의 CCTV 부터는 여러 개의 방향을 가질 수 있으므로 0, 1, 2, 3 네 가지 숫자로 표현할 수 없다고 생각할 수 있지만, 하나의 방향을 정한다면 나머지 방향은 정해지는 식으로 생각 할 수 있다.

예를 들어, 두번째 CCTV 의 경우 <- ->(* 기준) 으로 생각하면 된다. 이 방향을 기준으로 0, 1, 2, 3을 표현하면 나머지 방향은 저절로 결정된다. 

 

이런 방식으로 결정되면 0 ~ 4^8 - 1 까지로 8개의 CCTV 상태를 모두 표현할 수 있다. 나눗셈과 나머지 연산을 통해 특정 번째의 CCTV 의 방향을 구할 수 있다.

코드

package simulation;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BJ15683 {
    private static int N, M;
    private static int[][] map, copyMap;
    private static List<Point> startPoints = new ArrayList<>();

    private static int[] dx = {1, 0, -1, 0};
    private static int[] dy = {0, 1, 0, -1};
    private static int result = 0;

    public static void main(String[] args) throws IOException{
        readInput();
        solve();
    }
    
    private static void readInput()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];
        copyMap = 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] != 0 && map[i][j] != 6){
                    startPoints.add(new Point(i, j));
                }
            }
        }
    }

    private static void solve(){
        for(int status = 0; status  <  (1 << (2 * startPoints.size())); status++){
            for(int i = 0; i < N; i++){
                for(int j = 0; j < M; j++){
                    copyMap[i][j] = map[i][j];
                }
            }
            int temp = status;

            for(int i = 0; i < startPoints.size(); i++){
                int dir = temp % 4; 
                temp /= 4;
                Point p = startPoints.get(i);

                if(map[p.x][p.y] == 1){
                    light(p.x, p.y, dir);
                }
                else if(map[p.x][p.y] == 2){
                    light(p.x, p.y, dir);
                    light(p.x, p.y, (dir + 2) % 4);
                }
                else if(map[p.x][p.y] == 3){
                    light(p.x, p.y, dir);
                    light(p.x, p.y, (dir + 1) % 4);
                }
                else if(map[p.x][p.y] == 4){
                    light(p.x, p.y, dir);
                    light(p.x, p.y, (dir + 1) % 4);
                    light(p.x, p.y, (dir + 2) % 4);
                }
                else if(map[p.x][p.y] == 5){
                    light(p.x, p.y, 0);
                    light(p.x, p.y, 1);
                    light(p.x, p.y, 2);
                    light(p.x, p.y, 3);
                }
            }

            int cnt = 0;
            for(int i = 0; i < N; i++){
                for(int j = 0; j < M; j++){
                    if(copyMap[i][j] != 0) cnt++;
                }
            }

            result = Math.max(result, cnt);
        }

        System.out.println(N * M - result);
    }

    private static void light(int x, int y, int d){
        int nx = x;
        int ny = y;
        while(true){
            nx = nx + dx[d];
            ny = ny + dy[d];

            if(nx < 0 || nx >= N || ny < 0 || ny >= M)break;
            if(copyMap[nx][ny] == 6) break;
            copyMap[nx][ny] = 7;
        }
    }

    private static class Point{
        int x;
        int y;
        
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}

결과