Today I Learned

토요일에 있을 코테 준비!

외벽 점검

프로그래머스 2020 KAKAO BLIND RECRUITMENT 기출
https://school.programmers.co.kr/learn/courses/30/lessons/60062

문제

주어진 외벽은 원형으로 구성되어 있으며, 외벽의 길이는 n입니다.
친구들은 각각 이동 가능 거리가 다릅니다.
친구들은 외벽을 점검하기 위해 출발 지점을 임의로 선택하여 외벽을 따라 이동합니다.
외벽의 길이를 넘어가면 되돌아와서 점검할 수 있습니다.
친구들의 이동 가능 거리를 고려하여 최소한의 친구 수로 외벽을 점검하는 방법을 찾아야 합니다.

외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값을 return 하도록 solution 함수를 완성해주세요.

풀이 과정

• dist의 길이가 최대 8이므로, 완전 탐색을 이용해 가능한 모든 친구 배치를 고려하고, 그 중에서 가장 적은 친구 수로 외벽을 점검할 수 있는 경우를 찾아 풀어보았다.

1. DFS를 메소드를 나눌 목적이기 때문에 편리를 위해서 전역으로 설정할 변수를 초기화 해준다. 그리고 주어진 dist 배열을 오름차순으로 정렬한다. DFS 메서드를 호출 친구 배치를 완전 탐색한다.

2. DFS 메서드는 재귀적으로 작동하며, 시작 인덱스, 현재까지 점검 완료 개수, 사용한 친구 수를 매개변수로 받는다.

3. weak 개수 만큼 점검했다면 min 값과 현재 friends 값을 비교해 return 한다. 아니라면 계속 DFS를 진행한다.

4. back은 visit을 되돌리기 위해 방문한 인덱스를 저장하는 배열이다. 친구가 이동할 수 있는 거리와 count가 얼마나 증가했는지 저장하는 변수를 만드록 친구가 이동할 수 없을 때까지 while문을 돌린다. count가 취약 지점의 총 개수와 같아지면 모든 취약 지점을 점검한 것이므로 friends를 갱신하고 최소값을 업데이트한다.

5. 각 친구를 출발 지점으로 선택하여 외벽을 점검하는 과정을 반복한다. 각 친구마다 이동 가능한 거리 내에서 취약 지점을 점검하고, DFS를 재귀적으로 호출하여 다음 친구의 점검 상태를 확인한다. 최종적으로 최소 값이 반환된다.

Java 코드

import java.util.*;

class Solution {
  static int num;
  static int min = -1;
  static boolean[] visit;
  static int N;

  public int solution(int n, int[] weak, int[] dist) {
    N = n;
    num = weak.length;
    visit = new boolean[num];

    Arrays.sort(dist);

    DFS(dist.length - 1, 0, 1, weak, dist);
    return min;
  }

  static void DFS(int start, int count, int friends, int[] weak, int[] dist) {
    if(count == num) { 
      friends--;
      min = (min == -1) ? friends : Math.min(friends, min);
      return;
    }

    List<Integer> back = new ArrayList<>();

    if(start < 0) return;

    for(int i=0;i<num;i++) {
      if(visit[i]) continue;

      back.add(i);
      visit[i] = true;
      count++;

      int dis = dist[start];
      int temp = 1; 
      int idx = i;
      while(dis > 0 && count < num) { 
        if(visit[(idx + 1) % num]) break;

        int d = weak[(idx + 1) % num] - weak[idx];
        if(d < 0) d += N;

        dis -= d;

        if(dis >= 0) {
          temp++;
          count++;

          idx = (idx + 1) % num;
          back.add(idx);
          visit[idx] = true;
        }
      }

      DFS(start - 1, count, friends + 1, weak, dist);
      
      count -= temp;
      for(int b : back){
        visit[b] = false;
      }
      
      back.clear();
    }
  }
}