[프로그래머스/파이썬] 외벽 점검(60062) 풀이

---

• 프로그래머스 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 프로그래머스 코딩테스트 연습
• 문제 링크: 외벽 점검(60062)
• 문제풀이 코드 GitHub 링크
• 풀이 언어: Python 3

풀이

문제

원형 외벽의 취약 지점(weak)을 친구들의 이동 가능 거리(dist)로 모두 점검할 수 있는지 확인하고, 필요한 최소 친구 수를 구하는 문제입니다.

코드

from collections import deque
from bisect import bisect

def solution(n, weak, dist):
    dist = dist[::-1]
    ld = len(dist)
    weak = tuple(weak)
    
    q = deque([(weak, 0)])
    enQ = q.append
    deQ = q.popleft
    visited = set()
    visited.add(weak)

    while q:
        wps, i = deQ()
        for j in range(len(wps)):
            idx = bisect(wps, (wps[j]+dist[i])%n)
            tmpWps = wps[:j]+wps[idx:] if j < idx else wps[idx:j]
            ni = i+1
            if not tmpWps: return ni
            if ni < ld and tmpWps not in visited:
                enQ((tmpWps, ni))
                visited.add(tmpWps)

    return -1
            
print(solution(12, [1, 5, 6, 10], [1, 2, 3, 4]))

설명

남은 취약 지점 상태를 큐에 넣고 BFS로 탐색합니다.

한 상태에서 각 시작 취약점에 대해 현재 친구(dist[i])를 투입해 점검 가능한 구간을 제거한 다음, 남은 취약점 튜플을 다음 상태로 만듭니다.

취약점이 모두 제거되면 사용한 친구 수를 반환하고, 끝까지 불가능하면 -1을 반환합니다.

---

• 프로그래머스 문제풀이 전체 목록 보기

---