[백준] 15693번: 거짓말 - JAVA[자바]

안녕하세요.

오늘은  [백준] 15693번 : 거짓말  문제를 풀어보도록 하겠습니다.

📌 접근

 

이 문제는 모든 CCTV가 바라보는 방향의 조합을 완전 탐색(Brute Force) 으로 시도해,
사각지대(감시되지 않는 영역) 의 개수를 최소화하는 문제입니다.

 

1. CCTV 방향 조합 정의

CCTV는 번호(1~5)에 따라 감시 가능한 방향이 다릅니다.
각 CCTV가 감시할 수 있는 방향의 조합을 2진수 문자열(“상우하좌”) 형태로 정의했습니다.

예를 들어,

• "0001" → 왼쪽만 감시
• "0110" → 오른쪽과 아래 감시
• "1111" → 네 방향 모두 감시 (5번 CCTV)

이렇게 CCTV별 가능한 조합을 미리 선언해두면,
각 CCTV마다 가능한 회전 방향을 순회하며 탐색할 수 있습니다.

 

 

 

2. 방향 이동 정의

상하좌우 네 방향을 표현하기 위해 Node 클래스를 정의하고,
이를 direct 배열에 저장했습니다.

// 상(0), 우(1), 하(2), 좌(3)
public static final Node[] direct = {
    new Node(-1, 0),
    new Node(0, 1),
    new Node(1, 0),
    new Node(0, -1)
};

이후 "0101" 같은 문자열을 순회하면서
direct 배열의 각 방향에 맞게 CCTV가 감시할 칸을 탐색합니다.

 

 

 

3. CCTV 목록 수집

입력에서 0(빈칸), 6(벽), 1~5(CCTV 번호)를 읽습니다.
이때, CCTV의 좌표와 종류를 리스트(cctvs)에 저장해두고,
나머지는 grid 배열에 그대로 기록합니다.

if (grid[i][j] != 0 && grid[i][j] != 6) {
    cctvs.add(new Node(i, j));
}

 

 

 

4. 완전 탐색 (DFS)

CCTV가 여러 대일 경우, 각 CCTV의 방향 조합을 모두 시도해야 합니다.
이를 위해 DFS(깊이 우선 탐색) 을 사용했습니다.

• depth는 현재 탐색 중인 CCTV의 인덱스입니다.
• CCTV 하나의 모든 방향 조합(cctvComb)을 시도하면서,
  감시 가능한 칸을 visited 배열에 표시합니다.
• 한 CCTV의 방향 조합이 끝나면 다음 CCTV(depth+1)로 재귀 호출합니다.

public static void searchAll(int depth, boolean[][] visited) {
    if (depth == cctvs.size()) {
        int blind = getCnt(visited); // 사각지대 계산
        min = Math.min(min, blind);
        return;
    }

    Node pos = cctvs.get(depth);
    int kind = grid[pos.y][pos.x] - 1;

    for (String comb : cctvComb[kind]) {
        boolean[][] tmp = copy(visited); // 배열 복사
        for (int i = 0; i < 4; i++) {
            if (comb.charAt(i) == '1')
                go(direct[i], pos, tmp);  // 감시 영역 표시
        }
        searchAll(depth + 1, tmp);
    }
}

 

 

 

5. 감시 영역 표시

go() 함수는 CCTV가 바라보는 방향으로 계속 이동하면서,
벽(6)을 만나기 전까지의 모든 빈칸(0)을 감시 표시(visited = true) 합니다.

public static void go(Node dir, Node start, boolean[][] visited) {
    int y = start.y + dir.y;
    int x = start.x + dir.x;

    while (inRange(y, x) && grid[y][x] != 6) {
        if (grid[y][x] == 0)
            visited[y][x] = true;
        y += dir.y;
        x += dir.x;
    }
}

 

 

 

6. 사각지대 계산

모든 CCTV 방향이 정해진 후,
감시되지 않은 칸(grid[i][j] == 0 && !visited[i][j])의 개수를 세어
최소값을 갱신합니다.

 

💻 풀이

// hyeblee
import java.util.*;
import java.io.*;


public class Main {
    // 세로 n, 가로 m
    // n x m 정보
    // 0 빈칸, 6 벽, 1~5 cctv
    
    public static class Node {
        int y;
        int x;

        public Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    // 상(0) 우(1) 하(2) 좌(3) 방향 정보
    public static final Node[] direct 
    = {new Node(-1,0), new Node(0, 1), new Node(1,0), new Node(0, -1)};
    
    // cctv 별로 가능한 방향 조합, 0000(상우하좌)
    public static final String[][] cctvComb = {
        {"0001", "0010", "0100", "1000"}, // 1번 cctv
        {"0101", "1010"},
        {"0011", "0110", "1001", "1100"},
        {"0111", "1011", "1101", "1110"},
        {"1111"}
    };

    public static int n, m;
    public static List<Node> cctvs = new ArrayList<>();
    public static int[][] grid;
    public static int min = Integer.MAX_VALUE;

    public static boolean inRange(int y, int x) {
        return 0<=y && y<n && 0<=x && x<m;
    }

    // cctv 목록에서 종류 확인하고 모든 case 탐색돌리기
    public static void searchAll(int depth, boolean[][] visited) {
        if (depth == cctvs.size()) {
            // 사각지대 세기
            int result = getCnt(visited);
            min = Math.min(result, min);
            return;
        }

        
        Node pos = cctvs.get(depth);
        int y = pos.y;
        int x = pos.x;

        // System.out.println(y + ", "+x+": "+depth + "- kind "+ grid[y][x]);

        int kind = grid[y][x] - 1;
        for(String comb: cctvComb[kind]) {
            // 0001 처리?
            // 상우하좌
            boolean[][] tmp = new boolean[n][m];
            for(int j = 0;j<n;j++) {
                tmp[j] = Arrays.copyOf(visited[j], m);
            }
            for(int i=0;i<4;i++) {
                if (comb.charAt(i)=='1') {
                    go(direct[i], pos, tmp);
                }
                // print(tmp);
            }
            searchAll(depth+1, tmp);
        }
    }

    public static int getCnt(boolean[][] tmp) {
        int result = 0;

        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if (!tmp[i][j] && grid[i][j] == 0)
                    result++;;
            }
        }

        return result;
    }

    // start에서 시작하여 상하좌우 중 한 방향으로 계속 탐색해서 visited에 기록
    public static void go(Node direction, Node start, boolean[][] visited) {
        // System.out.printf("dirY: %d, dirX: %d\n", direction.y, direction.x);
        Node cur = new Node(start.y, start.x);

        while (true) {
            // 범위 벗어나거나 벽 만나면 break
            if (!inRange(cur.y, cur.x) || grid[cur.y][cur.x]==6) {
                break;
            }
            // 빈칸일때만 방문 기록 가능
            if (grid[cur.y][cur.x] == 0) {
                visited[cur.y][cur.x] = true;
            }
            // 전진
            cur.y += direction.y;
            cur.x += direction.x;
        }
    }


    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(new InputStreamReader(System.in));

        n = sc.nextInt();
        m = sc.nextInt();

        grid = new int[n][m];
        boolean[][] visited = new boolean[n][m];

        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                grid[i][j] = sc.nextInt();

                if (grid[i][j] != 0 && grid[i][j] != 6) { // 빈칸 아니거나 벽 아니면
                    cctvs.add(new Node(i,j));
                }
            }
        }

        searchAll(0, visited);
        System.out.println(min);
    }

}

 

🤔 고민했던 점 & 어려웠던 부분

더 예쁘고 짧게 짜고 싶었지만 저는 144줄이 최선이었습니다...

노가다 왕 힘들다 🥲🥲🥲