[Programmers] 2020 카카오 블라인드 채용 6번 - 외벽 점검

[문제 설명]

둘레가 n인 원 모양의 외벽이 주어진다.

보수가 필요한 지점을 담은 weak 배열이 주어질 때,

친구당 1시간 동안 이동할 수 있는 거리를 담은 dist 배열을 참고하여

모든 보수 지점을 점검할 수 있는 최소의 인원 수를 구하시오. (없는 경우 -1)

 

[조건]

1 <= n <= 200

1 <= len (weak) <= 15

1 <= len (dist) <= 8

 

[풀이 과정]

문제를 고민하다 보면 문제를 단순화시키는 몇 가지 중요한 점들을 알게 된다.

 

1. 수리가 필요한 곳은 한 점 단위이다.

장소 별로 수리에 필요한 길이가 다르지 않다.

이 점은 수리 장소를 탐색하는 것을 단순하게 해줄 수 있다.

 

2. 최소 인원 수를 구해야 한다.

따라서, 이동할 수 있는 거리가 가장 긴 친구부터 배치해야 한다.

 

3. 원 모양이므로 시계 방향과 반시계 방향으로 이동할 수 있다.

 

 

위의 사실들을 활용해서 문제를 해결하였는데,

가장 먼저 각 수리 지점 간의 간격을 저장하는 배열을 만들었다.

각 점마다 가장 가까운 지점까지의 거리를 시계 방향, 반시계 방향에 따라 저장한다.

(시계, 반시계 방향을 둘 다 살필 필요는 없었다.)

 

그리고, BFS를 구현하는데, 가장 먼 거리를 갈 수 있는 친구부터 배치한다.

아직 방문하지 않은 수리가 필요한 지점 (weak)을 찾고, 해당 지점에서 시계 방향과 반시계 방향으로 이동하였을 때 추가로 수리할 수 있는 지점을 체크하여 다시 Queue에 넣는다.

 

visit은 수리 지점이 15개 이하이므로, 비트마스킹을 활용하여 int 값으로 처리하였다.

굳이 비트마스킹을 하지 않고 배열로 처리해도 되지만, 메모리가 적게 들고 코드 가독성을 높이기 때문에 사용하였다.

추가로 수리할 수 있는 지점을 추가하는 코드 부분의 경우에는 시계 방향과 반시계 방향을 구분하여 구현해야 한다.

 

주의할 점은 Queue에서 가져오면서 정답 체크를 하는 것과 Queue에 넣기 전에 정답 체크를 하는 것의 차이가 크다는 점이다. 해당 방식의 풀이는 O (N!) 의 시간 복잡도를 갖기 때문에, 탐색의 깊이를 한 단계 줄이는 것은 큰 차이가 있다.

또한 앞선 탐색에서 동일한 수리를 진행하였다면 Queue에 넣지 않도록 처리해주어야 한다.

 

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Programmers_kakao2020_6_2 {
	// [함수] 취약 지점 사이의 거리 저장
    static void calculatingDistanceBetweenWeakpoint(int[][] distBetWeak, int[] weak, int n) {
        // 첫번째 지점
        distBetWeak[0][0] = weak[1] - weak[0];
        distBetWeak[0][1] = (n - weak[weak.length - 1]) + weak[0];

        // 중간 지점
        for (int i = 1; i < weak.length - 1; ++i) {
        	distBetWeak[i][0] = weak[i + 1] - weak[i]; // clock
        	distBetWeak[i][1] = distBetWeak[i - 1][0]; // Counter-Clock
        }
        
        // 마지막 지점
        distBetWeak[weak.length - 1][0] = distBetWeak[0][1];
        distBetWeak[weak.length - 1][1] = distBetWeak[weak.length - 2][0];
    }
	
    public static int solution(int n, int[] weak, int[] dist) {
        int answer = -1;
        boolean isVisit[] = new boolean[(1 << weak.length)];
        int distBetWeak[][] = new int[weak.length][2]; // [0] : clockwise, [1] : counter-clockwise
        
        calculatingDistanceBetweenWeakpoint(distBetWeak, weak, n);
        Arrays.sort(dist);
        
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {0, dist.length - 1}); // {visit, current longest friend index} 
        
        searching : while(!q.isEmpty()) {
        	int curVisit = q.peek()[0];
        	int curFriend = q.peek()[1];
        	q.poll();

        	// 방문 안한 지점부터 방문하기
        	for (int i = 0; i < weak.length; ++i) {
        		
        		if (((1 << i) & curVisit) == 0) {
        			for (int direction = 0; direction < 2; ++direction) { // clockwise : 0, counter-clockwise : 1
	        			int curI = i;
	        			int ableToGo = dist[curFriend];
	        			int newVisit = (1 << curI);
	        			
	        			while (true) {        			// 시계 방향
	        				if (ableToGo >= distBetWeak[curI][direction]) { // 더 수리할 수 있는 경우
	        					ableToGo -= distBetWeak[curI][direction];
	        					
	        					if (direction == 0) { // 시계 방향
		        					if (curI + 1 >= weak.length) {
		            					curI = -1;
		        					}
		        					newVisit |= (1 << (curI + 1));
		        					curI++;
	        					}
	        					else {                // 반시계 방향
		        					if (curI - 1 < 0) {
		            					curI = weak.length;
		        					}
		        					newVisit |= (1 << (curI - 1));
		        					curI--;
	        					}
	        				}
	        					
	        				else { // 수리를 더 이상 못하는 경우
	        					if (!isVisit[curVisit | newVisit]) {
	        						if ((curVisit | newVisit) == ((1 << weak.length) - 1)) { // 모든 취약 지점을 수리한 경우
	        			        		answer = (dist.length - 1) - curFriend + 1;
	        			        		break searching;
	        						}
	        			        	if (curFriend - 1 < 0) { // 모든 친구를 배정한 경우
	        			        		break;
	        			        	}
	        						isVisit[curVisit | newVisit] = true;
	        						q.add(new int[] {curVisit | newVisit, curFriend - 1});
	        					}
	        					break;
	        				}
	        			}
        			}
        		}
        	}
        }
        return answer;
    }
    
   public static void main(String[] args) {
//	   System.out.println(solution(12, new int[] {1, 5, 6, 10}, new int[] {1, 2, 3, 4}));
	   System.out.println(solution(12, new int[] {1, 3, 4, 9, 10}, new int[] {3, 5, 7}));
   }
}

 

 

 

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

코딩테스트 연습 - 외벽 점검