[프로그래머스] - 외벽 점검 (LEVEL 3)

programmers.co.kr/learn/courses/30/lessons/60062?language=python3

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

weak, dist 수가 많지 않아서 모든 weak point에서 시작해서 닿을 수 있는 경우에 대해 BFS로 푼 문제

 

<Solution>

from collections import deque
def solution(n, weak, dist):
    npoints=len(weak)
    dist.sort()
    indices=[i for i in range(npoints)]*2
    q=deque([[i,set(),set()] for i in range(npoints)])
    while q:
        idx,visit,friends = q.popleft()
        if len(visit)==npoints: return len(friends)
        if idx >= npoints: continue
        for i in set(range(len(dist))):
            if i in friends: continue
            for j in range(npoints-1,-1,-1):
                if (idx+j)%npoints in visit: continue
                dest = weak[indices[idx+j]]-weak[idx]
                if dest<0: dest+=n
                if dest<=dist[i]:
                    q.append([idx+j+1,visit|set(indices[idx:idx+j+1]),friends|{i}])
                    break
    return -1

 

<Solution2>

from collections import deque
def solution(n, weak, dist):
    dist.sort(reverse=True)
    v=set({tuple(weak)})
    q=deque([weak])
    for i in range(len(dist)): #모든 정점에 대해 큰 dist 부터 채워나감
        for _ in range(len(q)): #해당 차수의 모든 q를 pop()
            x=q.popleft() #방문해야 할 weak points
            for j in x:
                l=j; r=(l+dist[i])%n
                #방문하지 못한 weak points
                if l<r: temp = tuple(filter(lambda x: not (l<=x<=r),x))
                else: temp = tuple(filter(lambda x: r<x<l,x))
				
                if len(temp)==0: return i+1	#방문하지 못한 point가 없을 경우
                elif temp not in v:
                    q.append(temp)
                    v.add(tuple(temp))
    return -1