log 2021-09-28

---

• sport
  • bj 17352

sport

https://github.com/tony9402/baekjoon

백준 문제집 링크가 있어서, 이걸로 확인할 수가 있다! 이제 하나씩 풀면 될 듯하다.

bj 17352

https://www.acmicpc.net/problem/17352

hint

N개 원소에서 N-1 -> 트리 구조, 거기서 하나를 제외하면 두 개의 집합으로 나뉘어진다. 따라서, bfs로 한 집합을 탐색하고, 그 집합의 원소와, 그 집합에 있지 않은 원소 하나씩을 꺼내서 답으로 사용.

py solution

def solve():
    from collections import defaultdict

    N = ria()[0]
    set_all = set()
    set1 = set()
    set2 = set()

    adj = defaultdict(list)
    visited = [False] * (N+5)
    
    for i in range(N-2):
        a,b = ria()
        adj[a].append(b)
        adj[b].append(a)
    
    for i in range(1,N+1):
        set_all.add(i)
    
    q = [1]
    # bfs
    while(len(q)>0):
        next_item = q.pop()
        visited[next_item] = True
        set1.add(next_item)
        for nav in adj[next_item]:
            if(not visited[nav]):
                q.append(nav)
    # print(set1, set_all)
    set2 = set_all - set1
    
    item1 = set1.pop()
    item2 = set2.pop()
    print(item1, item2)
    
    return

---