[Week 5] FORTRESS self review - ChaeheeKang-GitHub

[chaeheekang]

FORTRESS self review

1. 해결 시도 과정

우선 성벽의 포함관계를 파악하기 위한 enclose 함수를 생성하였고,
이를 활용해 트리가 서로 연결되었는지 파악하는 함수까지는 구현이 가능하나

트리의 부모자식 관계 부분을 어떻게 해결해야 하는지 모르겠습니다.

2. 작성한 코드와 설명

하단의 함수는 성벽의 포함관계를 파악하는 함수이고

#성벽 a가 b를 포함하는지 확인
def enclose(a,b):
    #a와 b의 거리(루트연산 전)
    dist=(a[0]-b[0])**2 + (a[1]-b[1])**2
    #반지름의 길이(루트연산 전)
    r_dist=a[2]**2
    
    if r_dist>dist:
        return True

하단의 함수는 상단의 함수를 활용해 두 성벽이 연결되었는지 확인하는 함수 입니다.

def isChild(parent,child):
    if enclose(wall[parent],wall[child]):
        if isChild(parent,child)==False:
            connect[child]=True
        return True
    return False

3. 막힌 점 및 개선 사항

트리의 부모자식 관계를 해결해야할 것 같습니다.

[Queue-ri]

전 중첩한 children 리스트를 만들어서 각 정점의 인덱스 별로 자식 정점을 저장했습니다.
예를 들어 children[3] = [6,8] 이면

  3
 / \
6   8

이런 식의 구조를 의미합니다.
6주차에서 언급드린 일종의 인접리스트 같은 것입니다.

다만 enclose를 이용해서 자식인지 파악할때의 로직을 재귀로 구현하신다면 다소 까다로울 수도 있는데요,
저같은 경우엔 하단과 같이 구현했습니다. (먼저 내림차순으로 정렬부터 해주세요.)

Advanced-Algorithm-Study/DEF/FORTRESS/Queue-ri.py

Lines 35 to 38 in 3fc536c

	for i in range(1, N):
	if not connected[i]: # b is not connected yet
	if not grandchild(0, i):
	children[0].append(i)

문제에서 알 수 있는 점은 모든 성벽들이 하나의 커다란 외벽, 즉, 정점 0 안에 다 들어가있다는 사실이므로, 자식이든 손자(자식의 자식)든 일단 정점 0에게는 1~N-1까지의 정점이 다 연결될 것이 자명합니다.

따라서 여기선 enclose 같은 로직으로 굳이 판별하지 않고 바로 대상 정점이 정점 0의 손자인지만 파악하면 됩니다.

grandchild로 손자가 아닌 자식으로 판명되면 자신의 children으로 붙입니다.

참고로 connected는 그래프에서 visited 배열과 같은 역할입니다.

Advanced-Algorithm-Study/DEF/FORTRESS/Queue-ri.py

Lines 9 to 16 in 3fc536c

	def grandchild(adx, bdx):
	for chdx in children[adx]:
	if inner(wall[chdx], wall[bdx]):
	if not grandchild(chdx, bdx):
	children[chdx].append(bdx)
	connected[bdx] = True
	return True
	return False

grandchild는 b가 a의 손자인지 판별해주는 함수입니다. 손자인지 확인해보려면 b가 a의 자식에게도 enclose 되는지 체크해봐야 합니다. 따라서 a의 children 리스트를 쭉 돌면서 b가 enclose 되는지 계산해봅니다. 저는 enclose를 inner로 네이밍했습니다.

만약 enclose 걸리는게 있으면 일단 이 b는 a의 손자인 것이 맞고요, 하나도 걸리지 않으면 a의 자식인 것입니다. (return 문으로 표현되어 있습니다.)

그리고 만약 b가 a의 children 중에 한 정점(ch)과 enclose가 되면, 또다시 그 ch의 손자는 아닌지 재귀적으로 확인해보아야 합니다. 그래서 재귀함수가 쓰인 것이고.. 만약 여기서 재귀 호출된 grandchild가 False를 반환하면 이 b는 ch의 손자가 아니라 자식인거겠죠, 그럼 이 ch의 children 리스트에 b를 추가하고, visited 표시를 해줍니다.

P.S. 만약 재귀가 어렵다면 오름차순으로 정렬해서 거꾸로 정점 i 마다 부모를 찾고 바로 continue해서 다음 정점으로 넘어가는 방식으로도 구현해볼 수 있습니다. 물론 결국 트리의 지름을 구하는 과정에서 재귀를 사용해야 하기 때문에 가급적 하향식 풀이를 연습해보시는게 좋긴 하지만요.