아이템 줍기

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

[프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr](https://school.programmers.co.kr/learn/courses/30/lessons/87694)

아이템 줍기 문제 사각형 1~4개가 겹치게 주어지면 테두리만 따라 움직이면서 시작점과 도착점 최소 거리 구하는 문제

일단 그래프로 나타내기 위해 모든 좌표를 이어붙이는 작업을 한다 딕셔너리를 사용해서 현재 좌표를 키로 양쪽의 좌표 2개를 리스트로 넣어줌 교점이 발생하면 4개까지 늘어난다. 사각형의 테두리 안으로 들어갈 수 없어서 교점이 2개 보다 많아지면 없애줘야 한다 교점이 2개 초과인 것들만 가져와서 다음 노드 값이 어떤 사각형 안에 있던지 내부라고 판단되면 제거함 그리고 폭이나 길이가 1인 사격형은 내부에 속하지 않고 변에 속하기 때문에 현재 속하는 사각형으로 이어지는 노드는 모두 제거한다.

딕셔너리의 값으로 리스트를 사용해서 초기값설정과 각각 노드를 만드는데 반복적으로 코드가 길어짐 그래도 노드만 만들어지면 불가능한 경로는 제거하고 도착점까지 찾아가는 과정은 간단한편

def solution(r, cx, cy, ix, iy):
    d={}
    dr={}
    def f(x,y,k,m):
        return ((i[x]+k,i[y]),(i[x],i[y]+m))
    for n,i in enumerate(r):
        for j in range(i[0]+1,i[2]):
            d.setdefault((j,i[1]),[])
            d.setdefault((j,i[3]),[])
            dr.setdefault((j,i[1]),set())
            dr.setdefault((j,i[3]),set())
            d[(j,i[1])]+=[(j-1,i[1]),(j+1,i[1])]
            d[(j,i[3])]+=[(j-1,i[3]),(j+1,i[3])]
            dr[(j,i[1])].add(n)
            dr[(j,i[3])].add(n)
        for j in range(i[1]+1,i[3]):
            d.setdefault((i[0],j),[])
            d.setdefault((i[2],j),[])
            dr.setdefault((i[0],j),set())
            dr.setdefault((i[2],j),set())
            d[(i[0],j)]+=[(i[0],j+1),(i[0],j-1)]
            d[(i[2],j)]+=[(i[2],j+1),(i[2],j-1)] 
            dr[(i[0],j)].add(n)
            dr[(i[2],j)].add(n)
        d[(i[0],i[1])]=f(0,1,1,1)
        d[(i[0],i[3])]=f(0,3,1,-1)
        d[(i[2],i[1])]=f(2,1,-1,1)
        d[(i[2],i[3])]=f(2,3,-1,-1)
        dr[(i[0],i[1])]=set([n])
        dr[(i[0],i[3])]=set([n])
        dr[(i[2],i[1])]=set([n])
        dr[(i[2],i[3])]=set([n])


    g=list(filter(lambda x:len(x[1])>2,d.items()))
    g1=list(map(lambda x:x[0],g))

    for j in g:
        l=list(j[1])
        for k in l:
            for i in r:
                if (i[0]<k[0]<i[2] and i[1]<k[1]<i[3]):
                    if k in d[j[0]]:
                        d[j[0]].remove(k)

        if len(d[j[0]])>2:
            for k in l:
                for i in r:
                    if k in g1 and dr[k]-dr[j[0]]==set():
                        if k in d[j[0]]:
                            d[j[0]].remove(k)

    def ff(x,n,l):
        l+=[x]
        if x==(ix,iy):
            return n
        for i in d[x]:
            if i not in l:
                n=ff(i,n+1,l)
        return n

    a=ff(d[(cx,cy)][0],1,[(cx,cy)])
    b=ff(d[(cx,cy)][1],1,[(cx,cy)])
    return a if a<b else b