[4803] 트리 in python

 

> dfs

 

 

dfs 개념을 다시 짚고 넘어가자..

갑자기 막 헷갈림 ㅠㅠ

 

(1) 재귀함수를 이용한 dfs 구현

방문처리는 함수 맨 첫줄에...!

방문하지 않은 노드가 있다면 재귀함수만 호출시킴.

 

def dfs(node):
	visited[node]=False # 현재 노드 방문처리
    for i in array[node]: # 현재 노드와 연결된 노드들중에
    	if not visited[i]: # 방문하지 않은 노드가 있다면
        	dfs(i) # dfs(i) 재귀함수 호출

 

(2) stack을 이용한 dfs 구현

방문처리는 while문 안에서..! 

방문한 노드가 아닐 경우의 조건문 안에서!

def dfs_iteration(graph, root):
    visited = []
    stack = [root]
    while(stack): #스택에 남은것이 없을 때까지 반복
        node = stack.pop() # node : 현재 방문하고 있는 노드
        #현재 node가 방문한 적 없다 -> visited에 추가한다.
        #그리고 해당 node의 자식 node들을 stack에 추가한다.
        if(node not in visited):
            visited.append(node)
            stack.extend(graph[node])
    return visited


출처: https://juhee-maeng.tistory.com/25 [simPLE]

 

bfs와 dfs가 헷갈리면

아래 주소를 참고하기

https://eboong.tistory.com/467

[1260] DFS 와 BFS in python

---

 

이번 문제에서는

트리의 사이클을 찾아내는 게 쪼금 어려웠다...

사이클을 찾아내기 위해서

dfs 매개변수에 직전의 노드인 parent를 넘겨주어서

만약 해당 배열 안에 직전의 노드는 제외하고

dfs를 돌린다.

 

만약 해당 dfs 값이 이미 지나왔던 노드라면?

사이클이 존재하므로

False를 돌려준다. 

 

사이클이 존재하면 

트리가 아닌 것!

 

 

import sys
sys.setrecursionlimit(100000)
def dfs(node,parent):
    if visited[node]: # 사이클이 생긴 지점
        return False
    visited[node] = True # 방문 처리
    for i in array[node]:
        if i !=parent:
            if not dfs(i,node): # 사이클이 생긴 지점이라면
                return False # False
    return True

answer = 0
cnt = 0
while True:
    n,m=map(int,input().split())
    cnt += 1
    answer=0
    if n == 0 and m == 0:
        break
    array = [[] for _ in range(n + 1)]
    for i in range(m):
        a, b = map(int, input().split())
        array[a].append(b)
        array[b].append(a)
    visited = [False for _ in range(n + 1)]
    for i in range(1, n + 1):
        if visited[i]:
            continue
        if dfs(i,0):
            answer += 1
    if answer == 0:
        print("Case {}: No trees.".format(cnt))
    elif answer == 1:
        print("Case {}: There is one tree.".format(cnt))
    else:
        print("Case {}: A forest of {} trees.".format(cnt,answer))

 

실행속도를 약간 더 줄인 방법

 

import sys
sys.setrecursionlimit(100000)
def dfs(node,parent):
    visited[node] = True
    for i in array[node]:
        if i==parent: # 직전 노드에 해당하는 경우
            continue
        if visited[i]: # 방문 노드
            return False
        if not dfs(i,node): # dfs를 돌다가 사이클을 발견한 경우
            return False
    return True

answer = 0
cnt = 0
while True:
    n,m=map(int,input().split())
    cnt += 1
    answer=0
    if n == 0 and m == 0:
        break
    array = [[] for _ in range(n + 1)]
    for i in range(m):
        a, b = map(int, input().split())
        array[a].append(b)
        array[b].append(a)
    visited = [False for _ in range(n + 1)]
    for i in range(1, n + 1):
        if visited[i]:
            continue
        if dfs(i,0):
            answer += 1
    if answer == 0:
        print("Case {}: No trees.".format(cnt))
    elif answer == 1:
        print("Case {}: There is one tree.".format(cnt))
    else:
        print("Case {}: A forest of {} trees.".format(cnt,answer))