박시은

(❁´◡`❁)

8 분 소요


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


🔍 문제 풀이

문제 요약

  1. N x M 크기의 지도에 CCTV가 설치되어 있음
  2. cctv는 5가지 종류 있으며 최대 8개까지 설치 가능
  3. 각 CCTV는 고유한 감시 방향 조합을 가짐 (90도 회전 가능)
  4. CCTV가 감시할 수 있는 영역을 조합해 사각지대(0)의 최소 개수를 구하기


어떻게 풀까?

  1. 선택 가능한 방향 조합을 순회
  2. map[][]에 감시 영역 -1로 표시 (상태 변경)
  3. 변경된 상태로 dfs 재귀 호출
  4. dfs() 호출 후 map = copy(backup)으로 상태 복구 (백트래킹)
  5. 모든 조합을 검사한 뒤, 최소 사각지대 개수 min에 갱신


CCTV 종류별 감시 가능 방향

alt text

타입 감시 가능한 방향
1번 상, 하, 좌, 우 (1방향)
2번 상+하, 좌+우 (2방향)
3번 상+우, 우+하, 하+좌, 좌+상 (2방향)
4번 세 방향 조합 (4가지)
5번 상하좌우 모두 (1가지)


예제

0(빈공간), 2-5(CCTV 타입), 6(벽)

alt text

번호 위치(x, y) 타입 감시 방향 후보
1번 (1, 1) 2번 좌+우 or 상+하
2번 (3, 4) 2번 좌+우 or 상+하
3번 (5, 5) 5번 상하좌우 (고정)


백트래킹 순서

  1. dfs(0) -> (1,1)의 2번 CCTV
    • 감시 방향 조합: 상+하 또는 좌+우 → 총 2가지
  2. dfs(1) -> (3,4)의 2번 CCTV
    • 감시 방향 조합: 상+하 또는 좌+우 → 총 2가지
  3. dfs(2) -> (5,5)의 5번 CCTV
    • 감시 방향 고정: 상 + 하 + 좌 + 우 → 한 번만 감시
  4. dfs(3) -> 모든 CCTV 완료
  5. 현재 map 상태에서 사각지대(=0의 개수)를 계산하고 min 업데이트

alt text


CCTV 정보를 배열에 저장하는 이유

초기에는 CCTV를 찾자마자 바로 dfs(i, j)를 호출해 처리하려 했다.

  • 이렇게 하면 dfs(i, j)를 호출하면 그 자리의 CCTV는 처리할 수 있다.
  • 하지만,
    • 이전 CCTV가 어떤 방향 조합을 선택했는지를 기억하면서 다음 CCTV를 처리해야 하는데,
    • 다음 CCTV의 위치를 알 수 없기 때문에 모든 CCTV의 감시 방향 조합을 만들 수 없다.


결국 조합을 완성하기 전에 감시를 시작하게 되어 백트래킹이 불가능하다.

for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
        map[i][j] = Integer.parseInt(st.nextToken());

        if (map[i][j] >= 1 && map[i][j] <= 5) {
            dfs(i, j); // 여기서 바로 처리 -> 다음 CCTV의 위치를 모르기 때문에, 조합을 만들 수가 없음
        }
    }
}


그래서 모든 CCTV의 타입, 좌표를 배열에 따로 저장해 둔 후, dfs(0)을 호출하는 방식으로 변경했다.

  • 이렇게 하면 모든 CCTV를 순서대로 접근할 수 있다.
  • CCTV 정보를 순서대로 저장했기 때문에 dfs(0)부터 차례로 탐색해야 조합이 누락되지 않는다.
    • cctvType[0], cctvRow[0], cctvCol[0] : 첫 번째 CCTV
    • cctvType[1], ... : 두 번째 CCTV


⭐ 배운점

처음에는 다른 사람의 코드를 봐도 구조를 쉽게 이해하기 어려웠다.
특히 백트래킹과 CCTV 방향 처리 로직이 복잡하게 느껴졌다.

그래서 처음부터 직접 구현해보고, 하나씩 리팩토링하면서 구조를 내 방식대로 정리해봤다.

클래스를 쓰고, 방향 배열도 적용해보면서 어떤 방식이 더 효율적인지도 비교할 수 있었고, 결과적으로는 남의 코드보다 직접 리팩토링하는 과정이 더 큰 도움이 됐다.



💻 전체 코드 (리팩토링)

이제 구현한 코드를 기본적인 방식 -> 클래스 구조 도입 -> 방향 배열까지 적용하는 식으로 단계적으로 리팩토링해보자.

[1단계] 기본적인 방식

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

public class Main {
    static int n, m;
    static int[][] map;
    static int blindSpotMin = Integer.MAX_VALUE;

    static int[] dx = {0, -1, 0, 1}; // 우 상 좌 하
    static int[] dy = {1, 0, -1, 0};

    static int cctvCnt = 0;
    // CCTV 정보 -> 추후 클래스로
    static int[] cctvType = new int[8];
    static int[] cctvRow = new int[8];
    static int[] cctvCol = new int[8];

    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];

        // 1. 입력 및 cctv 정보 배열에 순서대로 저장
        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 (1 <= map[i][j] && map[i][j] <= 5) {
                    cctvType[cctvCnt] = map[i][j];
                    cctvRow[cctvCnt] = i;
                    cctvCol[cctvCnt] = j;
                    cctvCnt++;
                }
            }
        }

        // 2. 백트래킹 시작
        dfs(0); // 0번 CCTV부터
        System.out.println(blindSpotMin);
    }

    // cctvNum = 0이면 cctvRow[0], cctvCol[0], cctvType[0]을 사용
    // 다음 단계로 넘어가면 cctvNum++ 하면서 그 다음 CCTV를 처리
    static void dfs(int cctvNum) {
        if (cctvNum == cctvCnt) {
            blindSpotMin = Math.min(blindSpotMin, countBlindSpot());
            return;
        }

        int type = cctvType[cctvNum];
        int x = cctvRow[cctvNum];
        int y = cctvCol[cctvNum];

        int[][] backup = copyMap(map); // 현재 DFS 단계에서의 map 상태 백업

        // CCTV 유형별 감시 방향 처리
        if (type == 1) {
            for (int d = 0; d < 4; d++) { // 4방향 각각 탐색
                watch(x, y, d); // 현재 방향(d)로 감시
                dfs(cctvNum + 1); // 다음 CCTV 처리
                //  백트래킹마다 copyMap()을 호출해서 현재 map 상태를 백업
                map = copyMap(backup);// 백트래킹 후 다음 방향(d++) 감시
            }
        } else if (type == 2) {
            // d = 0일 때: 상 + 하, d = 1일 때: 우 + 좌
            for (int d = 0; d < 2; d++) { // 2가지 경우만 있음
                watch(x, y, d); // 첫 번째 방향 감시 (상 또는 우)
                watch(x, y, (d + 2) % 4);  // 반대 방향 감시 (하 또는 좌)
                dfs(cctvNum + 1); // 다음 CCTV 처리
                map = copyMap(backup);// 백트래킹 후 다음 방향(d++) 감시
            }
        } else if (type == 3) {
            for (int d = 0; d < 4; d++) {
                watch(x, y, d);
                watch(x, y, (d + 1) % 4);
                dfs(cctvNum + 1);
                map = copyMap(backup);
            }
        } else if (type == 4) {
            for (int d = 0; d < 4; d++) {
                watch(x, y, d);
                watch(x, y, (d + 1) % 4);
                watch(x, y, (d + 3) % 4);
                dfs(cctvNum + 1);
                map = copyMap(backup);
            }
        } else if (type == 5) {
            for (int d = 0; d < 4; d++) watch(x, y, d);
            dfs(cctvNum + 1);
            map = copyMap(backup);
        }
    }

    // 감시 처리
    static void watch(int x, int y, int dir) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        while (0 <= nx && nx < n && 0 <= ny && ny < m) {
            if (map[nx][ny] == 6) break; // 벽
            if (map[nx][ny] == 0) map[nx][ny] = -1; // 감시
            nx += dx[dir];
            ny += dy[dir];
        }
    }

    static int countBlindSpot() {
        int count = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (map[i][j] == 0) count++;
        return count;
    }

    // src라는 2차원 배열을 복사해서 새 배열로 만들어서 return
    static int[][] copyMap(int[][] src) {
        int[][] copy = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                copy[i][j] = src[i][j];
            }
        }
        return copy;
    }
}


[2단계] 클래스 도입

① CCTV 클래스를 새로 정의

class CCTV {
    int x, y, type;
    CCTV(int x, int y, int type) {
        this.x = x;
        this.y = y;
        this.type = type;
    }
}


② CCTV 정보를 배열에서 → 리스트로 전환

Before (1단계)

static int[] cctvType = new int[8];
static int[] cctvRow = new int[8];
static int[] cctvCol = new int[8];

After (2단계)

static List<CCTV> cctvs = new ArrayList<>();


③ 입력 처리 시 CCTV 객체로 추가

if (1 <= map[i][j] && map[i][j] <= 5) {
    cctvs.add(new CCTV(i, j, map[i][j]));
}


④ dfs()에서 CCTV 객체 활용

CCTV cctv = cctvs.get(cctvNum);
int x = cctv.x;
int y = cctv.y;
int type = cctv.type;


[3단계] dir 배열 도입

CCTV별 감시 방향 조합 배열 추가

static int[][][] cctvDir = {
    {}, // 0번 CCTV 없음
    {{0}, {1}, {2}, {3}}, // 1번
    {{0, 2}, {1, 3}}, // 2번
    {{0, 1}, {1, 2}, {2, 3}, {3, 0}}, // 3번
    {{0, 1, 2}, {1, 2, 3}, {2, 3, 0}, {3, 0, 1}}, // 4번
    {{0, 1, 2, 3}} // 5번
};


dfs() 함수 간결하게 변경

static void dfs(int cctvNum) {
    if (cctvNum == cctvs.size()) {
        blindSpotMin = Math.min(blindSpotMin, countBlindSpot());
        return;
    }

    CCTV cctv = cctvs.get(cctvNum);
    int x = cctv.x;
    int y = cctv.y;
    int type = cctv.type;

    int[][] backup = copyMap(map);

    for (int[] dirs : cctvDir[type]) {
        for (int d : dirs) {
            watch(x, y, d);
        }

        dfs(cctvNum + 1);
        map = copyMap(backup);
    }
}


전체 코드

훨씬 간결해졌다!

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

class CCTV{
    int x, y, type;
    CCTV(int x, int y, int type){
        this.x = x;
        this.y = y;
        this.type = type;
    }
}

public class Main {
    static int n, m;
    static int[][] map;
    static int blindSpotMin = Integer.MAX_VALUE;

    static int[] dx = {0, -1, 0, 1}; // 우 상 좌 하
    static int[] dy = {1, 0, -1, 0};

    static int[][][] cctvDir = {
            {}, // 0번 CCTV 없음
            {{0}, {1}, {2}, {3}},
            {{0, 2}, {1, 3}},
            {{0, 1}, {1, 2}, {2, 3}, {3, 0}},
            {{0, 1, 2}, {1, 2, 3}, {2, 3, 0}, {3, 0, 1}},
            {{0, 1, 2, 3}}
    };


    static List<CCTV> cctvs = new ArrayList<>();

    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 (1 <= map[i][j] && map[i][j] <= 5) {
                    cctvs.add(new CCTV(i, j, map[i][j]));
                }
            }
        }

        dfs(0);
        System.out.println(blindSpotMin);
    }

    static void dfs(int cctvNum) {
        if (cctvNum == cctvs.size()) {
            blindSpotMin = Math.min(blindSpotMin, countBlindSpot());
            return;
        }

        CCTV cctv = cctvs.get(cctvNum);
        int x = cctv.x;
        int y = cctv.y;
        int type = cctv.type;

        int[][] backup = copyMap(map); // 현재 DFS 단계에서의 map 상태 백업

        for (int[] dirs : cctvDir[type]) {
            for (int d : dirs) {
                watch(x, y, d);
            }

            dfs(cctvNum + 1);
            map = copyMap(backup);
        }
    }

    static void watch(int x, int y, int dir) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        while (0 <= nx && nx < n && 0 <= ny && ny < m) {
            if (map[nx][ny] == 6) break;
            if (map[nx][ny] == 0) map[nx][ny] = -1;
            nx += dx[dir];
            ny += dy[dir];
        }
    }

    static int countBlindSpot() {
        int count = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (map[i][j] == 0) count++;
        return count;
    }

    static int[][] copyMap(int[][] src) {
        int[][] copy = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                copy[i][j] = src[i][j];
            }
        }
        return copy;
    }
}


카테고리:

업데이트:

댓글남기기

참고