SWEA 5147 - Subtree

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVJ-_6qfsDFAWg&&#

처음 든 생각

- 부모와 자식 간의 관계임을 어떻게 나타낼까 -> [부모 , [자식들 노드] ] 형식으로 번호에 맞춰 매겨야겠다.

- subtree 노드 개수를 확인하기 위해 DFS를 해야겠네 -> DFS 코드 구현 어떻게 했더라...

 

나의 답

T = int(input())
for test_case in range(1, T + 1):
    E,N = map(int, input().split())
    tree =[ [0,[]] for _ in range(E+2)] 
    visited = [0 for _ in range(E+2)]
    a = list(map(int, input().split()))
    for i in range(0,len(a),2):
        tree[a[i]][1].append(a[i+1])
        tree[a[i+1]][0] = a[i]
        
    def dfs(v):
        global visited
        for i in tree[v][1]:
            if visited[i] == 0:
                visited[i] = 1
                dfs(i)          
    dfs(N)
    print(f"#{test_case} {sum(visited) + 1}")

 

 

노드의 숫자 번호를 그대로 사용하기 위해 E+2개의 노드와 방문 여부 리스트를 선언한다. 인덱스 0은 0번 노드가 없기 때문에 참조될 일이 없다.

 

간선은 2개씩 끊어서 비교해줘서 부모-자식 간의 관계를 할당해주면서 트리를 완성해주면 된다.

 

그 다음 기준 노드를 시작으로 DFS를 한다. 

DFS는 연결된 자식 노드들을 끝까지 타고 들어가면서 방문 여부를 체크해준다. 

 

다시 복습하면,

매개변수 = 시작 노드

연결된 노드들 반복문 돌면서

-> 방문 안했으면 그 노드 다시 DFS

-> 방문 했으면 패스

 

노드의 개수만 판단하면 되므로 visited의 총합을 출력하면 된다.

맨 처음 시작 노드를 빼먹어서 그냥 결과에 1을 더해주기로 했다.

 

트리구조 직접 만들어보고 DFS 복습하기 좋은 문제였다.