[백준] 4803번 : 트리 (파이썬)

DFS / Union Find 문제 

 

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

4803번: 트리

 

그래프에서 cycle이 존재하면 해당 그래프는 트리가 될 수 없다. 즉, 해당 문제는 어떠한 그래프가 주어졌을 때 cycle이 존재하는지의 여부를 구하고 트리의 갯수를 세는 문제이다. 이 문제는 union find나 dfs를 사용해서 풀 수 있다. 나는 이 문제를 총 2가지 방식으로 풀어보았다. 

 

(1) Union Find 이용

 

사실 이 문제는 학교 알고리즘 과목 기말고사에 유사하게 출제되었다. 그때도 union find를 사용하여 구현하였던 기억이 나 union find를 사용해선 금방 풀었다. mst 구현 방식에서 kruskal 기법을 이용하여 구현하면 된다. 

 

 

(2) DFS 이용

▪︎ 초기 코드 (틀림)  

# 트리 (골드4)
import sys
sys.setrecursionlimit(10000)
cnt = 1

while True:
    n, e = map(int, sys.stdin.readline().split())
    if n == 0 and e == 0: break

    graph = [[] for _ in range(n + 1)]
    parent = [0] * (n + 1)
    visited = [False for _ in range(n + 1)]
    tree = 0
    parentNode = []

    def dfs(x):
        global tree
        visited[x] = True
        for i in graph[x]:
            if visited[i] == False:
                parent[i] = x
                dfs(i)
            else:
                while parent[i] != 0:
                    if i == 0: break
                    i = parent[i]
                if i == x: # cycle
                    if x not in parentNode: 
                        parentNode.append(x) 
                        tree -= 1

    for _ in range(1, e + 1):
        l = list(map(int, sys.stdin.readline().split()))
        v1 = l[0]
        v2 = l[1]
        graph[v1].append(v2)
        graph[v2].append(v1)
    for i in range(1, n + 1):
        if visited[i] == True: continue
        tree += 1
        if len(graph[i]) != 0:
            dfs(i)
    
    if tree == 0:
        print(f"Case {cnt}: No trees.")
    elif tree == 1:
        print(f"Case {cnt}: There is one tree.")
    else:
        print(f"Case {cnt}: A forest of {tree} trees.")
    cnt += 1

 

일단 위의 코드로 계속 돌려보다가 도저히 어느 부분에서 틀린지 모르겠어서 백준 게시판에 있는 반례 및 실제 대회에 사용됐던 테스트 케이스를 일일이 다 훑어보았다. 그 중 8%대에서 한번, 75%대에서 한번 이렇게 총 두번 틀린 예시에 걸렸다.. 그 경우가 너무 궁금해 직접 찾아보았는데, 다음 그림 예시 중 2번과 같은 경우에서 계속 틀렸었다.

 

지금 보니까 왜이렇게 코드를 어렵게 짰는지 모르겠다.  그냥 cycle임을 판정하는 boolean 변수를 초기에 False로 두고 cycle = True가 되면 해당 그래프를 결과값에 안더해주면 된다. 근데 나는 왜 굳이 graph를 처음 탐색할 때부터 무조건 tree 변수를 1 더해주고 cycle이 판정된다면 tree 변수를 다시 1 빼주는 식으로 짰는지 모르겠다.  (사실 코드가 한번 틀리면 왜틀렸는지 고민해본 후 과감하게 지우고 개선해나가는 방식으로 짜야 되는데 , 나는 내 코드를 믿고 어떻게든 해당 코드를 살려보겠다고 새로운 변수를 추가하며 수정해나가는 식으로 짰었던거같다.)

한 그래프에서 사이클이 여러번 발견될 수도 있으므로 parentNode라는 리스트에 x를 추가해두고, x가 parentNode에 없을 때에만 tree에서 1을 빼준다. 처음에 이부분을 안넣었다가 tree의 수가 음수가 나와 놀랐었다.

 

ex1)

6 7
1 2 
1 4
2 3
3 4
4 5
3 6
5 6

위의 예시대로 그래프를 그려보면 위와 같이 나온다. 첫번째 그래프 그림은 예시를 보고 직관적으로 그린 그림이고, 두번째 그래프 그림은 dfs 방문순서에 맞게 그래프를 그린 그림이다. 

<실패코드>, <성공코드> 그림에서 빨간색 화살표는 dfs 호출하는 방향이고, 파란색 화살표는 dfs 호출해서 리턴할 때 실행되는 방향이다. 

또, 위의 그림에서 핑크색 형광펜 부분이 cycle을 형성하는 부분을 나타낸다. 위에선 양방향 그래프를 graph 변수에 저장하므로 dfs 호출하여 실행될 때나 리턴 뒤에 실행될 때 중 한번만 해당 cycle(핑크색 형광펜)을 발견하면 된다. 이를 위해 이미 방문한 노드일 경우, i == x라는 조건문을 두어 파란색 화살표 방향일 때만 cycle을 탐지하게 구현하였다. 여기서 노란색 형광펜 부분은 처음 방문한 노드인 경우이기 때문에 해당 로직이 실행될 리가 없다. 또, 하늘색 형광펜 부분에서 i는 x보다 값이 무조건 작으므로 이 역시 실행 안된다. 핑크색 형광펜 중 빨간색 화살표 방향도 마찬가지의 이유로 실행이 안된다. 결국엔 핑크색 형광펜 중 파란색 화살표 방향만 실행이 된다.

좀 더 자세히 얘기해보자면 x가 해당 노드고, i가 인접한 노드를  나타내는데 <실패코드>에서는 이 i를 0이 아닌 최상위부모까지 올라간 뒤 x와 비교한다. <성공코드>에서는 while문을 돌며 i를 부모노드의 값으로 치환하고 while문 안에서 x값과 i값(치환된 부모노드값)을 비교하며 같을 시에는 사이클이라고 판별한다.  

핑크색 형광펜에서 파란색 동그라미 친 부분이 해당 코드에서 걸려 로직을 수행했음을 의미한다.

결과적으로 <실패코드>와 <성공코드> 모두 정답은 맞게 나오지만(No trees.), 자세히 들여다보면  <실패코드>에서는 cycle 하나를 발견 못한다.

 

ex2)

4 4
2 3
3 4
4 2
1 2

<성공코드>의 경우 정답(No Trees.)가 맞게 나오지만, <실패코드>인 경우 오답(There is one tree)가 나온다. <실패코드>의 경우  i==x 판단 로직이 while문 밖에 있기 때문에 그렇다.

 

 

▪︎ 수정한 내 코드 (성공)

import sys
cnt = 1

while True:
    n, e = map(int, sys.stdin.readline().split())
    if n == 0 and e == 0: break

    graph = [[] for _ in range(n + 1)]
    parent = [0] * (n + 1)
    visited = [False for _ in range(n + 1)]
    tree = 0

    def dfs(x):
        global tree, cycle
        visited[x] = True
        for i in graph[x]:
            if not visited[i]:
                parent[i] = x
                dfs(i)
            else:
                while parent[i] != 0:
                    if i == 0: break
                    i = parent[i]
                    if i == x:  # cycle
                        cycle = True

    for _ in range(1, e + 1):
        l = list(map(int, sys.stdin.readline().split()))
        v1 = l[0]
        v2 = l[1]
        graph[v1].append(v2)
        graph[v2].append(v1)

    for i in range(1, n + 1):
        cycle = False
        if visited[i]: continue
        if len(graph[i]) != 0:
            dfs(i)
        if cycle == False:
            tree += 1

    if tree == 0:
        print(f"Case {cnt}: No trees.")
    elif tree == 1:
        print(f"Case {cnt}: There is one tree.")
    else:
        print(f"Case {cnt}: A forest of {tree} trees.")
    cnt += 1

 

i == x 확인 로직을 while문 안에 넣었고, dfs 재귀호출이 끝나고 cycle == False인 경우에만 tree의 수를 증가해시켰다.

 

(3) DFS 이용 - 위의 코드 리팩토링

import sys
cnt = 1

while True:
    n, e = map(int, sys.stdin.readline().split())
    if n == 0 and e == 0: break

    graph = [[] for _ in range(n + 1)]
    parent = [0] * (n + 1)
    visited = [False for _ in range(n + 1)]
    tree = 0

    def dfs(x):
        global tree, cycle
        visited[x] = True
        for i in graph[x]:
            if parent[x] == i: continue # 1) 방문한 적이 있지만, 인접 노드가 부모노드라면 사이클 X
            if visited[i] == True: # 2) 방문한 적이 있고, 그 이외의 경우는 cycle
                cycle = True
                break
            parent[i] = x # 3)
            dfs(i)

    for _ in range(1, e + 1):
        l = list(map(int, sys.stdin.readline().split()))
        v1 = l[0]
        v2 = l[1]
        graph[v1].append(v2)
        graph[v2].append(v1)

    for i in range(1, n + 1):
        cycle = False
        if visited[i]: continue
        if len(graph[i]) != 0:
            dfs(i)
        if cycle == False:
            tree += 1

    if tree == 0:
        print(f"Case {cnt}: No trees.")
    elif tree == 1:
        print(f"Case {cnt}: There is one tree.")
    else:
        print(f"Case {cnt}: A forest of {tree} trees.")
    cnt += 1

 

1) 인접 노드를 방문한 적이 있지만, 인접 노드가 부모 노드인 경우에는 사이클이 아니다. (양방향 그래프이므로 재방문할수밖에 없음.)

2) 인접 노드가 부모 노드가 아닌데, 해당 노드를 방문한 적이 있는 경우에는 사이클이다.

3) 1)2)의 경우는 continue나 break를 통해 for문을 빠져나가게 만듦. -> 1)2)의 경우가 아닌 경우는 처음 방문하는 경우로, parent배열에 부모노드의 값을 기록하고, dfs를 재귀호출한다.

 

해당 그래프에서 cycle이 하나라도 발견되면 break를 통해 그 즉시 for문을 빠져나오게 만들었다. 이를 통해 위의 코드에서보다 시간을 확연하게 줄일 수 있었다. (4100ms -> 236ms)

 

이게 정답을 맞추고 나니까 코드를 어떻게 리팩토링할지 쉽게 보이는것 같다.

 

느낀점 : 오답인 경우에는 근본적인 문제점을 알아내 문제를 해결하자 ..

 

*참고

https://www.acmicpc.net/board/view/107169

글 읽기 - 대회 테스트케이스

https://velog.io/@ledcost/%EB%B0%B1%EC%A4%80-4803-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%ED%8A%B8%EB%A6%AC-%EA%B3%A8%EB%93%9C-4-%ED%8A%B8%EB%A6%AC

[백준 4803 파이썬] 트리 (골드 4, 트리)

https://velog.io/@mechauk418/%EB%B0%B1%EC%A4%80-4803%EB%B2%88-%ED%8A%B8%EB%A6%AC-%ED%8C%8C%EC%9D%B4%EC%8D%AC%ED%8A%B8%EB%A6%AC

[백준] 4803번 트리 - 파이썬/트리