[완전탐색] 백준 3108 파이썬 풀이

 

백준 3108.

의식의 흐름 알고리즘

문제 자체는 쉽다. 어떤 규칙인지도 찾기는 쉽다.

주어진 점들로 사각형들을 다 그렸을 때, 이어서 그릴 수 있을만큼 그린다음 안되는 경우만 연필을 들면 되는 문제다.

예제3의 경우는 총 5개의 사각형이 있는데 꼭짓점이 맞닿으면 안떼고 사각형을 그릴 수 있다. 갔던 길은 중복해서 그을 수도 있다고 했기 때문에 꼭짓점이 아닌 모서리가 겹쳐도 안떼고 사각형을 그릴 수 있다는 점을 주의하자. 그래서 파란색으로 그은 사각형은 안떼고 갈 수 있으며 핑크색 사각형은 덩그러니 혼자 있으므로 한번 떼서 이동해야 한다.

 

이것도 이를테면 DFS느낌으로 가면 될 것 같다. 사각형들을 그렸을 때 겹치는 부분이나 맞닿는 부분이 하나라도 있으면 한번에 갈 수 있다. 아닌가 BFS인가..? A사각형에서 출발한다고 가정하고, 그 사각형과 겹치는지 안겹치는지를 다 체크해야 하지 않을까..?

 

여기서 잘못 접근한 발상 첫번째. 접하게 되는 조건을 고려를 했는데 접하지 않는 조건을 고려를 한다.

이것도 머리가 좀 팽팽 돌았는데 비교군1의 사각형이 검은색이라 가정하고 좌표도 (x1, y1)(x2, y2)로 가정을 하자. 그러고서 맞닿지 않게되는 경우의 수인 파란색 사각형이 총 6가지인데 이 때 x1,x2 / y1,y2는 작은 수대로 준다는 전제하에서 푸나보다. 문제에서 그런 조건은 없긴했는디..

#사방에 있는 사각형(1~4)인 경우 맞닿지 않는다고 본다.
if x4 < x1 or x3 > x2 or y2 < y3 or y4 < y1 :
    return False

#비교군 사각형 안에 폭 담긴다
if x1 < x3 and x2 > x4 and y4 < y2 and y3 > y1 :
    return False

#비교군 사각형을 담는다
if x1 > x3 and x2 < x4 and y4 > y2 and y3 < y1 :
    return False

 

솔직히 하나하나 다 적고나서야 안헷갈렸다ㅠ 아니 왤케 헷갈림..

 

아무튼 그다음에 고려할 것은 두번째. 서로 서로가 접하는 관계인 것을 어떻게 기록할 것인가. 유니온파인드라는 것을 사용한다고 한다. 그래프 알고리즘으로 두 노드 간에 연결관계(접한다)가 있다면 이어주는 그런 형태인 셈. 유니온파인드에 대해 알고싶다면

    #유니온 파인드의 기본 규칙 - 인덱스와 같은 값의 value의 배열을 만듦    
    parent = [i for i in range(n)]

    def find(i):
        if i != parent[i]:
            return find(parent[i])
        else:
            return i
        
    def union(a, b):
        a = find(a)
        b = find(b)
        if a < b :
            parent[b] = a
            parent[a] = b

 

유니온을 하여 부모노드를 설정하고, 최종적으로 같은 부모노드를 가지고 있는지 확인하는 과정까지.

 

이런 일련의 과정을 거쳐서 parent에는 [0,0,0,0,4] 가 남게되고 한붓그리기로 가능한게 총 두 조합이라는 것이 나오는데 시작점이 0,0인 경우는 처음 펜을 놓은 상태 그대로 출발할 수 있기에 총 수에서 -1을 해줘야 하는 것 까지 고려해주면 된다.

 

 

틀린답

def bf13():
    n = int(input())
    sqr = []
    chk = False
    for _ in range(n):
        x1, y1, x2, y2 = map(int, input().split())
        if x1==0 and y1 ==0 or x2==0 and y2==0 :
            chk = True
        sqr.append(((x1,y1), (x2,y2)))
    
    #유니온 파인드의 기본 규칙 - 인덱스와 같은 값의 value의 배열을 만듦    
    parent = [i for i in range(n)]
    
    def meet(a, b):
        x1, y1, x2, y2 = a[0][0], a[0][1], a[1][0], a[1][1]
        x3, y3, x4, y4 = b[0][0], b[0][1], b[1][0], b[1][1]
        #사방에 있는 사각형(1~4)인 경우 맞닿지 않는다고 본다.
        if x4 < x1 or x3 > x2 or y2 < y3 or y4 < y1 :
            return False

        #비교군 사각형 안에 폭 담긴다
        if x1 < x3 and x2 > x4 and y4 < y2 and y3 > y1 :
            return False

        #비교군 사각형을 담는다
        if x1 > x3 and x2 < x4 and y4 > y2 and y3 < y1 :
            return False
    
        return True
    
    def find(i):
        if i != parent[i]:
            return find(parent[i])
        else:
            return i
        
    def union(a, b):
        a = find(a)
        b = find(b)
        if a < b :
            parent[b] = a
        else:
            parent[a] = b
    
    for i in range(n-1):
        for j in range(i+1, n):
            if meet(sqr[i], sqr[j]):
                #몇 번 째 사각형끼리 union인지
                union(i, j)
    
    for i in range(n):
        find(i)
    
    #parent배열에서 동일한 숫자끼리 set으로 묶어 총 숫자 몇개의 조합인지 판별
    res = len(set(parent))
    if chk :
        print(res -1)
    else:
        print(res)

 

 

 

최종 알고리즘

다른 풀이들을 봐도 영 모르겠어서 한참을 뒤지고 또 뒤지다가

        x1, y1, x2, y2 = map(int, input().split())
        if x1==0 or x2 ==0 :
            if y1 <= 0 <= y2:
                chk = True
        if y1==0 or y2 == 0:
            if x1<= 0 <= x2:
                chk = True

 

        if aa < bb :
            parent[bb] = aa
        else:
            parent[aa] = bb

 

    cnt = 0
    for i in range(n):
        if parent[i] == i:
            cnt+=1
            
    if chk :
        print(cnt -1)
    else:
        print(cnt)

 

이 두부분을 고치고 나서야 해결이 되었다. 아니 사실 이렇게 풀거면 sqr에 set으로 저장할 필요도 없음.

뭔가 형식 상 그게 좋아보여서(?) set으로 했는데 필요 없는 작업이었고 set을 이용하려면 union에서 조금 다르게 처리를 해줘야 하는 듯 한데 이해가 안됨... 참고

 

set이 아닌 단순히 부모 노드를 본인 인덱스에 맞는 위치에 선언하는 방식

def bf13():
    n = int(input())
    sqr = []
    chk = False
    for _ in range(n):
        x1, y1, x2, y2 = map(int, input().split())
        if x1==0 or x2 ==0 :
            if y1 <= 0 <= y2:
                chk = True
        if y1==0 or y2 == 0:
            if x1<= 0 <= x2:
                chk = True
        sqr.append(((x1,y1), (x2,y2)))
    
    #유니온 파인드의 기본 규칙 - 인덱스와 같은 값의 value의 배열을 만듦    
    parent = [i for i in range(n)]
    
    def meet(a, b):
        x1, y1, x2, y2 = a[0][0], a[0][1], a[1][0], a[1][1]
        x3, y3, x4, y4 = b[0][0], b[0][1], b[1][0], b[1][1]
        #사방에 있는 사각형(1~4)인 경우 맞닿지 않는다고 본다.
        if x4 < x1 or x3 > x2 or y2 < y3 or y4 < y1 :
            return False

        #비교군 사각형 안에 폭 담긴다
        if x1 < x3 and x2 > x4 and y4 < y2 and y3 > y1 :
            return False

        #비교군 사각형을 담는다
        if x1 > x3 and x2 < x4 and y4 > y2 and y3 < y1 :
            return False
    
        return True
    
    def find(i):
        if i != parent[i]:
            parent[i] = find(parent[i])
        return parent[i]
        
    def union(a, b):
        aa = find(a)
        bb = find(b)
        if aa < bb :
            parent[bb] = aa
        else:
            parent[aa] = bb
    
    for i in range(n-1):
        for j in range(i+1, n):
            if meet(sqr[i], sqr[j]):
                #몇 번 째 사각형끼리 union인지
                union(i, j)

    cnt = 0
    for i in range(n):
        if parent[i] == i:
            cnt+=1
            
    if chk :
        print(cnt -1)
    else:
        print(cnt)

 

와 아니 근데 골드단계부터는 정말.. 너무..어렵다...............................................................