[프로그래머스] 외벽 점검

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/60062

문제 풀이

• DFS, 비트마스킹을 이용하여 풀이하였다.
• 문제 풀이 방법은 다음과 같다.

  • 모든 취약지점 간의 거리를 인접행렬로 정의 (시계, 반시계 한쪽 방향으로 선택하여 정의)
  • 가장 이동거리가 긴 인원부터 내림차순으로 아래 반복 (순열)
    - 모든 취약지점을 시작점으로 고려하여 특정 방향으로 진행했을때 도달 가능한 지점 체크해줌
    - 모든 취약지점이 체크되었으면 최소값 갱신
    - 다음 이동거리가 긴 인원으로 넘어감
  • 이 때 취약지점을 체크해주는 로직은 비트마스킹으로 구현하였다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int N, result = Integer.MAX_VALUE;
    public int[] W;
    public int[] D;
    public int[][] adj;
    public int chk; //비트마스킹

    public void dfs (int ind) {
        if (ind < 0) return;
        if (D.length - ind >= result) return;

        int dist = D[ind];
        //모든 취약점을 시작점으로 고려
        for (int i = 0; i < W.length; i++) {
            if ((chk & (1 << i)) == (1 << i)) continue;
            //1. 모든 타겟에 대해 체크해줌
            int plus = 0;
            for (int t = 0; t < W.length; t++) {
                if ((chk & (1 << t)) == (1 << t)) continue;
                if (adj[i][t] <= dist) {
                    chk += (1 << t);
                    plus += (1 << t);
                }
            }
            //2. 모든 취약점이 체크되었는지 파악
            if (chk == ((1 << W.length) - 1))  {
                result = D.length - ind;
                chk -= plus;
                return;
            }
            dfs(ind - 1);
            //3. 모든 타겟 체크 해제
            chk -= plus;
        }
    }

    public int solution(int n, int[] weak, int[] dist) {
        //초기화
        N = n;
        W = weak;
        D = dist;
        adj = new int[W.length][W.length];
        for (int i = 0; i < W.length; i++) {
            for (int j = 0; j < W.length; j++) {
                if (i == j) continue;
                if (i < j) {
                    adj[i][j] = W[j] - W[i];
                } else {
                    adj[i][j] = N + W[j] - W[i];
                }
            }
        }

        //DFS
        Arrays.sort(D);
        dfs(D.length - 1);
        if (result == Integer.MAX_VALUE) return -1;
        else return result;
    }
}