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

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

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

중복없이 전체 탐색을 해야하는 까다로운 문제입니다. 

 

우선 문제부터 간단하게 요약하면, 

다음과 같이 원의 각각 모서리 마다 weak한 지점들이 있는데 사람들을 보내서 이 weak한 지점들을 모두 탐색하는 최소인원수를 구해야하는 문제입니다. 링크를 들어가 문제를 읽어보는 것을 추천합니다. 

 

solution(n, weak, dist) 안에

n : 외벽의 길이

weak : 취약 지점의 위치가 담긴 오름차순 배열

dist : 각 친구가 1시간 동안 이동할 수 있는 거리

가 주어질 때, 취약지점을 모두 탐색할 수 있는 최소 사람수를 return 하여야 합니다. 만약 탐색이 불가능 한 경우에는 -1을 return 해야 합니다. 

 

정답을 설명하면서, 주의해야하는점과, 해메었던 부분에 대해서도 설명해 보겠습니다. 

 

<Solution>

우선 가장 처음 이 문제를 접하였을 때 들었던 생각들을 정리해보면 다음과 같습니다. 

1. 멀리 이동할 수 있는 친구부터 배정하는게 좋지 않을까? 2. 시계방향과 반시계 방향 이렇게 각각 search를 진행하면 될 것 같다

이렇게 두 가지 아이디어를 처음 가지고 문제를 풀기 시작하였습니다. 

 

우선 1번 "멀리 이동할 수 있는 친구부터 배정" 이 방식은 맞습니다. 하지만 2번 "시계방향과 반시계 방향 모두 고려해야한다" 이것은 틀린 이야기 입니다. 시계방향과 반시계 방향의 search를 각각 한다고 생각해보고, 시계방향으로만 search를 진행한다고 생각하였을 때, 둘의 경우는 결과적으로 같아지는 것을 알 수 있습니다. (최종적으로 사라진 weak point들을 생각해서 비교한다고 생각하면 편함)

위의 그림에 따라 시계방향만 고려해도 괜찮다는 결론이 나오게 됩니다. 

 

가장 처음 양쪽 방향 모두를 찾는 dfs로 구현을 하였는데 이러한 경우 시간 초과가 많이 발생하게 됩니다. 

<잘못된 풀이>(양쪽 방향 모두 찾음) 

def solution(n, weak, dist):
    answer = int(1e9)
    # fast answer
    if max(dist)>=n:
        return 1
    
    reverse_dist = sorted(dist)[::-1]
    stack = [[weak, 0]] # weak, num_people
    while(stack):
        # print(f'current_stack : {stack}')
        pop_w, pop_t = stack.pop()
        if len(pop_w) == 0:
            if pop_t < answer:
                answer = pop_t
        if pop_t >= answer or pop_t >= len(dist):
            continue
        for w in pop_w:
            # remove searched weak points
            # right, left
            new_w_r = []
            new_w_l = []
            temp_list_r = [_%n for _ in range(w,w+reverse_dist[pop_t]+1)]
            temp_list_l = [_%n for _ in range(w,w-reverse_dist[pop_t]-1,-1)]
            for w_ in pop_w:
                # print(f'current w_ : {w_}')
                # right
                if w_ in temp_list_r:
                    pass
                else:
                    new_w_r.append(w_)
                # left
                if w_ in temp_list_l:
                    pass
                else:
                    new_w_l.append(w_)
            stack.append([new_w_r, pop_t+1])
            stack.append([new_w_l, pop_t+1])

    if answer == int(1e9):
        return -1
    else: 
        return answer

그렇다면 한 방향을 찾는 방식으로 진행하면 괜찮아 지는지 코드를 구현해 보았습니다. 하지만 이 때의 경우에도 시간초과에 걸리게 됩니다. 또한 위의 코드에서 temp_list_r과 temp_list_l안에 있는지 in 으로 비교하는 부분도 시간이 많이 걸릴 것 같아 수정했음에도 계속 시간초과에 걸리게 됩니다. 

 

그렇다면 이 문제를 어떻게 풀어야 할까요? 

 

최종적인 솔루션은 (사실 dfs bfs상관없음) bfs를 사용하였고, bfs큐에 넣기전에 현재 weak와 넣은 사람수가 같아지는(사람수는 가장 dist가 큰 사람부터 넣음) 경우들을 (중복제거) 제거하는 형태로 구현하였습니다. 

(test case 13,14에서 계속 막힌다면 굵은 글씨를 시도해보세요) 

 

사실 문제를 풀다가 코드가 꼬여서 조금 복잡해 보이기는 하는데 제가 풀어본 결과로 dfs나 bfs로 구현할 때 가장 중요한 아이디어는 아직 탐색되지 않은 weak포인트들과 이미 들어간 사람이 같아지는 경우들을 중복 카운팅 하지 않아야 하는 것 같습니다. 이 점을 착안해서 문제를 풀면 조금 더 깔끔하고, 시간도 덜 드는 코드가 나올 것 같습니다. 

 

실제 구현한 코드는 아래와 같습니다. 밑줄치거나 굵은 글씨의 아이디어 위주로 코드를 보면 될 것 같고 이 점들만 지키면 다른 가지치기 없이도 충분히 빠르게 통과 될 것 같습니다. 더불어 다른 더 좋은 풀이들도 있으나 혹시나 dfs나 bfs로 하시는데 안되면 아래와 같이 해보시면 될 것 같습니다.

 

<올바른 풀이>

from collections import deque

def solution(n, weak, dist):
    answer = int(1e9)
    # fast answer
    if max(dist)>=n:
        return 1
    
    reverse_dist = sorted(dist)[::-1]
    q = deque([(tuple(weak), 0)]) # weak, num_people

    pop_t_default = 0
    index = 0
    while(1):
        temp_append_list = []
        while(q):
            pop_w, pop_t = q.popleft()
            if len(pop_w) == 0:
                return answer
            else: 
                for w in pop_w:
                    # print(f'-------current w!!! : {w}-----')
                    # remove searched weak points
                    # right side only
                    new_w = []
                    for w_ in pop_w:
                        # print(f'current w_ : {w_}')
                        if w<=w_<=(w+reverse_dist[pop_t]) or w<=(w_+n)<=(w+reverse_dist[pop_t]):
                            pass
                        else:
                            new_w.append(w_)
                        
                    if len(new_w) != 0 and pop_t+1 < answer and pop_t+1 < len(dist):
                        temp_append_list.append((tuple(new_w), pop_t+1))
                    else:
                        if len(new_w) == 0:
                            if pop_t+1 < answer:
                                answer = pop_t+1
        if len(temp_append_list) == 0:
            break
        for element in list(set(temp_append_list)):
            q.append(element)

    if answer == int(1e9):
        return -1
    else: 
        return answer