6416 트리인가

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

save_cases = {}
count = 0
while True :

    temp_list = list(input().split())

    if str(-1) in temp_list:
        break
    elif len(temp_list) == 0 :
        count+=1
    else :
        temp_list = list(map(int,temp_list))
        if save_cases.get(count) is None :
            save_cases[count] = temp_list
        else :
            save_cases[count] += temp_list

from collections import deque

def check_tree(now_list):

    now_queue = deque(now_list)
    now_graph = {}
    overlap_graph = {}
    overlap_graph2 = {}

    for pop_q in range(len(now_list)):
        start = now_queue.popleft()
        end = now_queue.popleft()

        if start == 0 or end == 0 :
            break

        if now_graph.get(start) is None :
            now_graph[start] = [end]
        else :
            now_graph[start] += [end]

        if overlap_graph.get(start) is None:
            overlap_graph[start] = 0
            overlap_graph2[start] = 0
        if overlap_graph.get(end) is None:
            overlap_graph[end] = 0
            overlap_graph2[end] = 0

    # overlap_graph는 0이 하나고 나머지는 다 1이어야한다.
    # 우선 루트를 찾아야하니까 bfs로 돌면서 방문하지 않는 곳이 있는지 확인하자.
    q = deque()
    if len(now_graph.keys()) == 0 :
        return 1
    temp_list = list(now_graph.keys())
    for t in temp_list:
        q.append(now_graph[t])
    while q :
        now = q.popleft()
        for n in now :
            overlap_graph[n] += 1
    if list(overlap_graph.values()).count(0) != 1 :
        return -1
    else :
        temp_ = list(overlap_graph.keys())
        root_idx = list(overlap_graph.values()).index(0)
        root_node = temp_[root_idx]

        # root를 찾았으면 이 root를 기점으로 bfs를 다시 전개해서 count를 하자.

        last_q = deque()
        last_q.append(now_graph[root_node])
        while last_q :
            now_q = last_q.popleft()
            for nq in now_q :
                overlap_graph2[nq] += 1
                if now_graph.get(nq) is None :
                    last_q.append([])
                else :
                    last_q.append(now_graph[nq])

        if max(overlap_graph2.values()) != 1 :
            return -1
        else :
            return 1

f = 1

for i in range(len(save_cases.keys())) :
    now_list = save_cases[i]
    if check_tree(now_list) == 1:
        print("Case {} is a tree.".format(f))
    else :
        print("Case {} is not a tree.".format(f))
    f+=1

3. 풀이 및 생각

문제 풀이

이 문제는 약간 트리를 풀기 위해 BFS를 할줄 알아야하고, 내 생각이지만 시뮬레이션도 잘해야할 것 같다. 문제 자체는 꽤나 복잡한데, 일단 입력 받는 것부터가 문제다. 내 경우에는 while문을 써서 조건문을 통해 데이터 케이스들을 받았다.

근데 첩첩산중이라했나, 뒤에 트리인지 아닌지를 파악하는 것도 문제였다. 트리를 파악하는 조건은 다음과 같다.

1. 루트 노드가 하나여야한다.
2. 중복해서 들어오는 간선을 가지면 안된다.

그래서 나는 BFS를 두번 사용했다. 하나는 루트노드를 먼저 찾기 위해 사용했고, 다른 하나는 루트노드를 찾은 후 이것은 기점으로 다른 노드들을 탐방해서 중복되는 것이 있는지 확인했다.

그리고 추가적으로 한가지 추가할 것이 있었는데, 입력이

0 0 
-1 -1

이렇게 들어오면 트리라고 판명해야한다는 것이다. 이걸 추가 안하면 채점율 33%에서 틀리게 되더라.

나의 생각

와우 이 문제 코드를 짜면서 절대로 이렇게 코드를 짜는게 아닌거 같음을 알았지만, 일단 해결부터 해보자하고 문제를 풀었다. 근데 어찌저찌 하다보니 풀게되긴했는데, 질문 검색란을 보니 CYCLE인 것은 예제에 추가되지 않았다고 사람들이 이야기한다.. 그래서 막상 내것도 해보면 cycle 예제에선 문제가 발생한다. 그러나 백준 사이트 측에선 이것을 문제의 취지로 보지 않는 것 같다..(?) 그래서 나도 일단은 이 문제를 넘기기로 했다.