[프로그래머스/자바] 외벽 점검 풀이 - 2020 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

2020 KAKAO BLIND RECRUITMENT Level 3 문제다.

 

 

 

 

DFS를 통해 가장 긴 거리를 갈 수 있는 친구부터 취약 지점을 점검한다.

그러기 위해서는 dist를 내림차순 정렬해야 하지만,

내림차순(Collections.reverseOrder()) 정렬은 int 자료형으로는 불가능하므로 (Integer로 변환해야 함) 

먼저 오름차순 정렬하고, 뒤에서부터 0까지 DFS를 진행했다.

 

DFS로 점검할 친구의 인덱스, 점검 완료 갯수, 친구 수를 전달한다.

점검할 친구가 갈 수 있는 거리만큼 시계 방향으로 돌면서 점검을 완료한다.

점검을 완료할 때마다 cnt를 증가시켜 점검을 완료한 갯수를 구하고,

 

 

그리고 점검할 친구가 갈 수 있는 거리만큼 다 돌았는데 

아직 점검할 취약 지점이 남았다면, 

다음으로 가장 긴 거리를 갈 수 있는 친구가 다시 시계 방향으로 돌면서 점검을 하고

점검 완료 갯수가 점검해야 할 취약 지점의 갯수와 같아질 때까지 DFS를 재귀적으로 돈다.

점검 완료 갯수가 점검해야 할 취약 지점의 갯수와 같아지면 최소 친구 수를 갱신한다.

 

DFS의 첫번째 매개변수인 점검할 친구의 인덱스가 dist의 배열 범위를 벗어나면,

해당 방법으로는 모든 취약 지점을 점검할 수 없는 것이므로 바로 return한다.

 

 

문제 상에서는 시계/반시계 방향 두가지를 모두 사용했지만 코드 상에서는 한 가지 방향으로만 구현해도 된다.

입출력 예#2에서,

4m에서 점검을 시작하면 반시계 방향으로 돌아야 모두 점검할 수 있지만

9m에서 점검을 시작하고 시계 방향으로 돌아도 모두 점검할 수 있다.

어차피 DFS로 모든 경우를 고려할 것이기 때문에 시계/반시계로 나눌 필요 없이

시계 방향으로만 돌아도 제대로 답을 구할 수 있다.

 

 

배운점 및 느낀점

n, weak, dist의 최대 크기가 크지 않기 때문에 브루트포스 중 DFS를 사용했다.

테스트 케이스 만들고 breakpoint 찍어가며 디버깅 하니까 그렇게 어렵지 않은 문제였다.

실행속도가 좀 느린 것 같아서 다른 코드들 참고해서 다시 구현해봐야겠다.

 

 

 

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 cnt, int f, int[] weak, int[] dist) {
		if(cnt == num) { // 취약 정점 갯수만큼 점검했다면
			f--;
			min = min == -1 ? f : Math.min(f, min);
			return;
		}

		// visit를 되돌리기 위해 방문한 인덱스 저장
		ArrayList<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;
			cnt++;
			
			int dis = dist[start]; // 친구가 이동할 수 있는 거리
			int temp = 1; // cnt를 되돌리기 위해 cnt가 얼마나 증가했는지 저장
			int idx = i;
			while(dis > 0 && cnt < num) { // 친구가 이동할 수 없을 때까지
				if(visit[(idx + 1) % num]) 
					break;
				
				int disDiff = weak[(idx + 1) % num] - weak[idx];
				if(disDiff < 0)
					disDiff += N;

				dis -= disDiff;

				if(dis >= 0) {
					temp++;
					cnt++;
					
					idx = (idx + 1) % num;
					back.add(idx);
					visit[idx] = true;
				}
			}

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